lib/Image.cc

   1 // -*- mode: C++; indent-tabs-mode: nil; c-basic-offset: 2; -*-
   2 // Image.cc for Blackbox - an X11 Window manager
   3 // Copyright (c) 2001 - 2005 Sean 'Shaleh' Perry <shaleh@debian.org>
   4 // Copyright (c) 1997 - 2000, 2002 - 2005
   5 //         Bradley T Hughes <bhughes at trolltech.com>
   6 //
   7 // Permission is hereby granted, free of charge, to any person obtaining a
   8 // copy of this software and associated documentation files (the "Software"),
   9 // to deal in the Software without restriction, including without limitation
  10 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
  11 // and/or sell copies of the Software, and to permit persons to whom the
  12 // Software is furnished to do so, subject to the following conditions:
  13 //
  14 // The above copyright notice and this permission notice shall be included in
  15 // all copies or substantial portions of the Software.
  16 //
  17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  20 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  22 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  23 // DEALINGS IN THE SOFTWARE.
  24
  25 #include "Image.hh"
  26 #include "Display.hh"
  27 #include "Pen.hh"
  28 #include "Texture.hh"
  29
  30 #include <algorithm>
  31 #include <vector>
  32
  33 #include <X11/Xlib.h>
  34 #include <X11/Xutil.h>
  35 #ifdef    MITSHM
  36 #  include <sys/types.h>
  37 #  include <sys/ipc.h>
  38 #  include <sys/shm.h>
  39 #  include <unistd.h>
  40 #  include <X11/extensions/XShm.h>
  41 #endif // MITSHM
  42
  43 #include <assert.h>
  44 #include <math.h>
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47
  48 // #define COLORTABLE_DEBUG
  49 // #define MITSHM_DEBUG
  50
  51
  52 static unsigned int right_align(unsigned int v)
  53 {
  54   while (!(v & 0x1))
  55     v >>= 1;
  56   return v;
  57 }
  58
  59 static int lowest_bit(unsigned int v)
  60 {
  61   int i;
  62   unsigned int b = 1u;
  63   for (i = 0; ((v & b) == 0u) && i < 32;  ++i)
  64     b <<= 1u;
  65   return i == 32 ? -1 : i;
  66 }
  67
  68
  69 unsigned int bt::Image::global_maximumColors = 0u; // automatic
  70 bt::DitherMode bt::Image::global_ditherMode = bt::OrderedDither;
  71
  72
  73 namespace bt {
  74
  75   class XColorTable {
  76   public:
  77     XColorTable(const Display &dpy, unsigned int screen,
  78                 unsigned int maxColors);
  79     ~XColorTable(void);
  80
  81     inline bt::DitherMode ditherMode(void) const
  82     {
  83       return ((n_red < 256u || n_green < 256u || n_blue < 256u)
  84               ? bt::Image::ditherMode()
  85               : bt::NoDither);
  86     }
  87
  88     void map(unsigned int &red,
  89              unsigned int &green,
  90              unsigned int &blue);
  91     unsigned long pixel(unsigned int red,
  92                         unsigned int green,
  93                         unsigned int blue);
  94
  95   private:
  96     const Display &_dpy;
  97     unsigned int _screen;
  98     int visual_class;
  99     unsigned int n_red, n_green, n_blue;
 100     int red_shift, green_shift, blue_shift;
 101
 102     std::vector<unsigned long> colors;
 103   };
 104
 105
 106   typedef std::vector<unsigned char> Buffer;
 107   static Buffer buffer;
 108
 109
 110   typedef std::vector<XColorTable*> XColorTableList;
 111   static XColorTableList colorTableList;
 112
 113
 114   void destroyColorTables(void) {
 115     XColorTableList::iterator it = colorTableList.begin(),
 116                              end = colorTableList.end();
 117     for (; it != end; ++it) {
 118       if (*it)
 119         delete *it;
 120       *it = 0;
 121     }
 122     colorTableList.clear();
 123     buffer.clear();
 124   }
 125
 126
 127 #ifdef MITSHM
 128   static XShmSegmentInfo shm_info;
 129   static bool use_shm = false;
 130   static bool shm_attached = false;
 131   static int shm_id = -1;
 132   static char *shm_addr = reinterpret_cast<char *>(-1);
 133
 134
 135   static int handleShmError(::Display *, XErrorEvent *) {
 136     use_shm = false;
 137     return 0;
 138   }
 139
 140
 141   void startupShm(const Display &display) {
 142     // query MIT-SHM extension
 143     if (!XShmQueryExtension(display.XDisplay()))
 144       return;
 145     use_shm = true;
 146   }
 147
 148
 149   void destroyShmImage(const Display &display, XImage *image) {
 150     // tell the X server to detach
 151     if (shm_attached) {
 152       XShmDetach(display.XDisplay(), &shm_info);
 153
 154       // wait for the server to render the image and detach the memory
 155       // segment
 156       XSync(display.XDisplay(), False);
 157
 158       shm_attached = false;
 159     }
 160
 161     // detach shared memory segment
 162     if (shm_addr != reinterpret_cast<char *>(-1))
 163       shmdt(shm_addr);
 164     shm_addr = reinterpret_cast<char *>(-1);
 165
 166     // destroy shared memory id
 167     if (shm_id != -1)
 168       shmctl(shm_id, IPC_RMID, 0);
 169     shm_id = -1;
 170
 171     // destroy XImage
 172     image->data = 0;
 173     XDestroyImage(image);
 174   }
 175
 176
 177   XImage *createShmImage(const Display &display, const ScreenInfo &screeninfo,
 178                          unsigned int width, unsigned int height) {
 179     if (!use_shm)
 180       return 0;
 181
 182     // use MIT-SHM extension
 183     XImage *image = XShmCreateImage(display.XDisplay(), screeninfo.visual(),
 184                                     screeninfo.depth(), ZPixmap, 0,
 185                                     &shm_info, width, height);
 186     if (!image)
 187       return 0;
 188
 189     // get shared memory id
 190     unsigned int usage = image->bytes_per_line * image->height;
 191     shm_id = shmget(IPC_PRIVATE, usage, IPC_CREAT | 0644);
 192     if (shm_id == -1) {
 193 #ifdef MITSHM_DEBUG
 194       perror("bt::createShmImage: shmget");
 195 #endif // MITSHM_DEBUG
 196
 197       use_shm = false;
 198       XDestroyImage(image);
 199       return 0;
 200     }
 201
 202     // attached shared memory segment
 203     shm_addr = static_cast<char *>(shmat(shm_id, 0, 0));
 204     if (shm_addr == reinterpret_cast<char *>(-1)) {
 205 #ifdef MITSHM_DEBUG
 206       perror("bt::createShmImage: shmat");
 207 #endif // MITSHM_DEBUG
 208
 209       use_shm = false;
 210       destroyShmImage(display, image);
 211       return 0;
 212     }
 213
 214     // tell the X server to attach
 215     shm_info.shmid = shm_id;
 216     shm_info.shmaddr = shm_addr;
 217     shm_info.readOnly = True;
 218
 219     static bool test_server_attach = true;
 220     if (test_server_attach) {
 221       // never checked if the X server can do shared memory...
 222       XErrorHandler old_handler = XSetErrorHandler(handleShmError);
 223       XShmAttach(display.XDisplay(), &shm_info);
 224       XSync(display.XDisplay(), False);
 225       XSetErrorHandler(old_handler);
 226
 227       if (!use_shm) {
 228         // the X server failed to attach the shm segment
 229
 230 #ifdef MITSHM_DEBUG
 231         fprintf(stderr, "bt::createShmImage: X server failed to attach\n");
 232 #endif // MITSHM_DEBUG
 233
 234         destroyShmImage(display, image);
 235         return 0;
 236       }
 237
 238       test_server_attach = false;
 239     } else {
 240       // we know the X server can attach to the memory segment
 241       XShmAttach(display.XDisplay(), &shm_info);
 242     }
 243
 244     shm_attached = true;
 245     image->data = shm_addr;
 246     return image;
 247   }
 248 #endif // MITSHM
 249
 250 } // namespace bt
 251
 252
 253 bt::XColorTable::XColorTable(const Display &dpy, unsigned int screen,
 254                              unsigned int maxColors)
 255   : _dpy(dpy), _screen(screen),
 256     n_red(0u), n_green(0u), n_blue(0u),
 257     red_shift(0u), green_shift(0u), blue_shift(0u)
 258 {
 259   const ScreenInfo &screeninfo = _dpy.screenInfo(_screen);
 260   const Visual * const visual = screeninfo.visual();
 261   const Colormap colormap = screeninfo.colormap();
 262
 263   visual_class = visual->c_class;
 264
 265   bool query_colormap = false;
 266
 267   switch (visual_class) {
 268   case StaticGray:
 269   case GrayScale:
 270     {
 271       if (visual_class == GrayScale) {
 272         if (maxColors == 0u) {
 273           // inspired by libXmu...
 274           if (visual->map_entries > 65000)
 275             maxColors = 4096;
 276           else if (visual->map_entries > 4000)
 277             maxColors = 512;
 278           else if (visual->map_entries > 250)
 279             maxColors = 12;
 280           else
 281             maxColors = 4;
 282         }
 283
 284         maxColors =
 285           std::min(static_cast<unsigned int>(visual->map_entries), maxColors);
 286         n_red = n_green = n_blue = maxColors;
 287       } else {
 288         n_red = n_green = n_blue = visual->map_entries;
 289         query_colormap = true;
 290       }
 291
 292       colors.resize(n_green);
 293
 294       const unsigned int g_max = n_green - 1;
 295       const unsigned int g_round = g_max / 2;
 296
 297       for (unsigned int g = 0; g < n_green; ++g) {
 298         colors[g] = ~0ul;
 299
 300         if (visual_class & 1) {
 301           const int gray = (g * 0xffff + g_round) / g_max;
 302
 303           XColor xcolor;
 304           xcolor.red   = gray;
 305           xcolor.green = gray;
 306           xcolor.blue  = gray;
 307           xcolor.pixel = 0ul;
 308
 309           if (XAllocColor(_dpy.XDisplay(), colormap, &xcolor))
 310             colors[g] = xcolor.pixel;
 311           else
 312             query_colormap = true;
 313         }
 314       }
 315       break;
 316     }
 317
 318   case StaticColor:
 319   case PseudoColor:
 320     {
 321       if (visual_class == PseudoColor) {
 322         if (maxColors == 0u) {
 323           // inspired by libXmu...
 324           if (visual->map_entries > 65000)
 325             maxColors = 32 * 32 * 16;
 326           else if (visual->map_entries > 4000)
 327             maxColors = 16 * 16 * 8;
 328           else if (visual->map_entries > 250)
 329             maxColors = visual->map_entries - 125;
 330           else
 331             maxColors = visual->map_entries;
 332         }
 333
 334         maxColors =
 335           std::min(static_cast<unsigned int>(visual->map_entries), maxColors);
 336
 337         // calculate 2:2:1 proportions
 338         n_red   = 2u;
 339         n_green = 2u;
 340         n_blue  = 2u;
 341         for (;;) {
 342           if ((n_blue * 2u) < n_red
 343               && (n_blue + 1u) * n_red * n_green <= maxColors)
 344             ++n_blue;
 345           else if (n_red < n_green
 346                    && n_blue * (n_red + 1u) * n_green <= maxColors)
 347             ++n_red;
 348           else if (n_blue * n_red * (n_green + 1u) <= maxColors)
 349             ++n_green;
 350           else
 351             break;
 352         }
 353       } else {
 354         n_red   = right_align(visual->red_mask)   + 1;
 355         n_green = right_align(visual->green_mask) + 1;
 356         n_blue  = right_align(visual->blue_mask)  + 1;
 357         query_colormap = true;
 358       }
 359
 360       colors.resize(n_red * n_green * n_blue);
 361
 362       const int r_max = n_red - 1;
 363       const int r_round = r_max / 2;
 364       const int g_max = n_green - 1;
 365       const int g_round = g_max / 2;
 366       const int b_max = n_blue - 1;
 367       const int b_round = b_max / 2;
 368
 369       // create color cube
 370       for (unsigned int x = 0, r = 0; r < n_red; ++r) {
 371         for (unsigned int g = 0; g < n_green; ++g) {
 372           for (unsigned int b = 0; b < n_blue; ++b, ++x) {
 373             colors[x] = ~0ul;
 374
 375             if (visual_class & 1) {
 376               XColor xcolor;
 377               xcolor.red   = (r * 0xffff + r_round) / r_max;
 378               xcolor.green = (g * 0xffff + g_round) / g_max;
 379               xcolor.blue  = (b * 0xffff + b_round) / b_max;
 380               xcolor.pixel = 0ul;
 381
 382               if (XAllocColor(_dpy.XDisplay(), colormap, &xcolor))
 383                 colors[x] = xcolor.pixel;
 384               else
 385                 query_colormap = true;
 386             }
 387           }
 388         }
 389       }
 390       break;
 391     }
 392
 393   case TrueColor:
 394     n_red   = right_align(visual->red_mask)   + 1;
 395     n_green = right_align(visual->green_mask) + 1;
 396     n_blue  = right_align(visual->blue_mask)  + 1;
 397
 398     red_shift = lowest_bit(visual->red_mask);
 399     green_shift = lowest_bit(visual->green_mask);
 400     blue_shift = lowest_bit(visual->blue_mask);
 401     break;
 402
 403   case DirectColor:
 404     // from libXmu...
 405     n_red = n_green = n_blue = (visual->map_entries / 2) - 1;
 406     break;
 407   } // switch
 408
 409 #ifdef COLORTABLE_DEBUG
 410   switch (visual_class) {
 411   case StaticGray:
 412   case GrayScale:
 413     for (int x = 0; x < colors.size(); ++x) {
 414       const int gray = (x * 0xffff + (n_green - 1) / 2) / (n_green - 1);
 415       fprintf(stderr, "%s %3u: gray %04x\n",
 416               colors[x] == ~0ul ? "req  " : "alloc", x, gray);
 417     }
 418     break;
 419   case StaticColor:
 420   case PseudoColor:
 421     for (int x = 0; x < colors.size(); ++x) {
 422       int r = (x / (n_green * n_blue)) % n_red;
 423       int g = (x / n_blue) % n_green;
 424       int b = x % n_blue;
 425
 426       r = (r * 0xffff + (n_red - 1) / 2) / (n_red - 1);
 427       g = (g * 0xffff + (n_green - 1) / 2) / (n_green - 1);
 428       b = (b * 0xffff + (n_blue - 1) / 2) / (n_blue - 1);
 429
 430       fprintf(stderr, "%s %3u: %04x/%04x/%04x\n",
 431               colors[x] == ~0ul ? "req  " : "alloc", x, r, g, b);
 432     }
 433     break;
 434   default:
 435     break;
 436   }
 437 #endif // COLORTABLE_DEBUG
 438
 439   if (colors.empty() || !query_colormap)
 440     return;
 441
 442   // query existing colormap
 443   const int depth = screeninfo.depth();
 444   int q_colors = (((1u << depth) > 256u) ? 256u : (1u << depth));
 445   XColor queried[256];
 446   for (int x = 0; x < q_colors; ++x)
 447     queried[x].pixel = x;
 448   XQueryColors(_dpy.XDisplay(), colormap, queried, q_colors);
 449
 450 #ifdef COLORTABLE_DEBUG
 451   for (int x = 0; x < q_colors; ++x) {
 452     if (queried[x].red == 0
 453         && queried[x].green == 0
 454         && queried[x].blue == 0
 455         && queried[x].pixel != BlackPixel(_dpy.XDisplay(), _screen)) {
 456       q_colors = x;
 457       break;
 458     }
 459
 460     fprintf(stderr, "query %3u: %04x/%04x/%04x\n",
 461             x, queried[x].red, queried[x].green, queried[x].blue);
 462   }
 463 #endif // COLORTABLE_DEBUG
 464
 465   // for missing colors, find the closest color in the existing colormap
 466   for (unsigned int x = 0; x < colors.size(); ++x) {
 467     if (colors[x] != ~0ul)
 468       continue;
 469
 470     int red, green, blue, gray;
 471
 472     switch (visual_class) {
 473     case StaticGray:
 474     case GrayScale:
 475       red = green = blue = gray =
 476             (x * 0xffff - (n_green - 1) / 2) / (n_green - 1);
 477       break;
 478     case StaticColor:
 479     case PseudoColor:
 480       red = (x / (n_green * n_blue)) % n_red;
 481       green = (x / n_blue) % n_green;
 482       blue = x % n_blue;
 483
 484       red = (red * 0xffff + (n_red - 1) / 2) / (n_red - 1);
 485       green = (green * 0xffff + (n_green - 1) / 2) / (n_green - 1);
 486       blue = (blue * 0xffff + (n_blue - 1) / 2) / (n_blue - 1);
 487
 488       gray = ((red * 30 + green * 59 + blue * 11) / 100);
 489       break;
 490     default:
 491       assert(false);
 492     }
 493
 494     int mindist = INT_MAX, best = -1;
 495     for (int y = 0; y < q_colors; ++y) {
 496       const int r = (red - queried[y].red) >> 8;
 497       const int g = (green - queried[y].green) >> 8;
 498       const int b = (blue - queried[y].blue) >> 8;
 499       const int dist = (r * r) + (g * g) + (b * b);
 500
 501       if (dist < mindist) {
 502         mindist = dist;
 503         best = y;
 504       }
 505     }
 506     assert(best >= 0 && best < q_colors);
 507
 508 #ifdef COLORTABLE_DEBUG
 509     fprintf(stderr, "close %3u: %04x/%04x/%04x\n",
 510             x, queried[best].red, queried[best].green, queried[best].blue);
 511 #endif // COLORTABLE_DEBUG
 512
 513     if (visual_class & 1) {
 514       XColor xcolor = queried[best];
 515
 516       if (XAllocColor(_dpy.XDisplay(), colormap, &xcolor)) {
 517         colors[x] = xcolor.pixel;
 518       } else {
 519         colors[x] = gray < SHRT_MAX
 520                     ? BlackPixel(_dpy.XDisplay(), _screen)
 521                     : WhitePixel(_dpy.XDisplay(), _screen);
 522       }
 523     } else {
 524       colors[x] = best;
 525     }
 526   }
 527 }
 528
 529
 530 bt::XColorTable::~XColorTable(void) {
 531   if (!colors.empty()) {
 532     XFreeColors(_dpy.XDisplay(), _dpy.screenInfo(_screen).colormap(),
 533                 &colors[0], colors.size(), 0);
 534     colors.clear();
 535   }
 536 }
 537
 538
 539 void bt::XColorTable::map(unsigned int &red,
 540                           unsigned int &green,
 541                           unsigned int &blue) {
 542   red   = (red   * n_red)   >> 8;
 543   green = (green * n_green) >> 8;
 544   blue  = (blue  * n_blue)  >> 8;
 545 }
 546
 547
 548 unsigned long bt::XColorTable::pixel(unsigned int red,
 549                                      unsigned int green,
 550                                      unsigned int blue) {
 551   switch (visual_class) {
 552   case StaticGray:
 553   case GrayScale:
 554     return colors[(red * 30 + green * 59 + blue * 11) / 100];
 555
 556   case StaticColor:
 557   case PseudoColor:
 558     return colors[(red * n_green * n_blue) + (green * n_blue) + blue];
 559
 560   case TrueColor:
 561   case DirectColor:
 562     return ((red << red_shift)
 563             | (green << green_shift)
 564             | (blue << blue_shift));
 565   }
 566
 567   // not reached
 568   return 0; // shut up compiler warning
 569 }
 570
 571
 572 bt::Image::Image(unsigned int w, unsigned int h)
 573   : data(0), width(w), height(h)
 574 {
 575   assert(width > 0);
 576   assert(height > 0);
 577 }
 578
 579
 580 bt::Image::~Image(void) {
 581   free(data);
 582   data = 0;
 583 }
 584
 585
 586 Pixmap bt::Image::render(const Display &display, unsigned int screen,
 587                          const bt::Texture &texture) {
 588   if (texture.texture() & bt::Texture::Parent_Relative)
 589     return ParentRelative;
 590   if (texture.texture() & bt::Texture::Solid)
 591     return None;
 592   if (!(texture.texture() & bt::Texture::Gradient))
 593     return None;
 594
 595   Color from, to;
 596   bool interlaced = texture.texture() & bt::Texture::Interlaced;
 597
 598   if (texture.texture() & bt::Texture::Sunken) {
 599     from = texture.color2();
 600     to = texture.color1();
 601   } else {
 602     from = texture.color1();
 603     to = texture.color2();
 604   }
 605
 606   data = static_cast<RGB *>(malloc(width * height * sizeof(RGB)));
 607
 608   if (texture.texture() & bt::Texture::Diagonal)
 609     dgradient(from, to, interlaced);
 610   else if (texture.texture() & bt::Texture::Elliptic)
 611     egradient(from, to, interlaced);
 612   else if (texture.texture() & bt::Texture::Horizontal)
 613     hgradient(from, to, interlaced);
 614   else if (texture.texture() & bt::Texture::Pyramid)
 615     pgradient(from, to, interlaced);
 616   else if (texture.texture() & bt::Texture::Rectangle)
 617     rgradient(from, to, interlaced);
 618   else if (texture.texture() & bt::Texture::Vertical)
 619     vgradient(from, to, interlaced);
 620   else if (texture.texture() & bt::Texture::CrossDiagonal)
 621     cdgradient(from, to, interlaced);
 622   else if (texture.texture() & bt::Texture::PipeCross)
 623     pcgradient(from, to, interlaced);
 624
 625   if (texture.texture() & (bt::Texture::Sunken | bt::Texture::Raised))
 626     bevel(texture.borderWidth());
 627
 628   Pixmap pixmap = renderPixmap(display, screen);
 629
 630   unsigned int bw = 0;
 631   if (texture.texture() & bt::Texture::Border) {
 632     Pen penborder(screen, texture.borderColor());
 633     bw = texture.borderWidth();
 634
 635     for (unsigned int i = 0; i < bw; ++i) {
 636       XDrawRectangle(penborder.XDisplay(), pixmap, penborder.gc(),
 637                      i, i, width - (i * 2) - 1, height - (i * 2) - 1);
 638     }
 639   }
 640
 641   return pixmap;
 642 }
 643
 644
 645 /*
 646  * Ordered dither table
 647  */
 648 static const unsigned int dither16[16][16] = {
 649   {     0, 49152, 12288, 61440,  3072, 52224, 15360, 64512,
 650       768, 49920, 13056, 62208,  3840, 52992, 16128, 65280 },
 651   { 32768, 16384, 45056, 28672, 35840, 19456, 48128, 31744,
 652     33536, 17152, 45824, 29440, 36608, 20224, 48896, 32512 },
 653   {  8192, 57344,  4096, 53248, 11264, 60416,  7168, 56320,
 654      8960, 58112,  4864, 54016, 12032, 61184,  7936, 57088 },
 655   { 40960, 24576, 36864, 20480, 44032, 27648, 39936, 23552,
 656     41728, 25344, 37632, 21248, 44800, 28416, 40704, 24320 },
 657   {  2048, 51200, 14336, 63488,  1024, 50176, 13312, 62464,
 658      2816, 51968, 15104, 64256,  1792, 50944, 14080, 63232 },
 659   { 34816, 18432, 47104, 30720, 33792, 17408, 46080, 29696,
 660     35584, 19200, 47872, 31488, 34560, 18176, 46848, 30464 },
 661   { 10240, 59392,  6144, 55296,  9216, 58368,  5120, 54272,
 662     11008, 60160,  6912, 56064,  9984, 59136,  5888, 55040 },
 663   { 43008, 26624, 38912, 22528, 41984, 25600, 37888, 21504,
 664     43776, 27392, 39680, 23296, 42752, 26368, 38656, 22272 },
 665   {   512, 49664, 12800, 61952,  3584, 52736, 15872, 65024,
 666       256, 49408, 12544, 61696,  3328, 52480, 15616, 64768 },
 667   { 33280, 16896, 45568, 29184, 36352, 19968, 48640, 32256,
 668     33024, 16640, 45312, 28928, 36096, 19712, 48384, 32000 },
 669   {  8704, 57856,  4608, 53760, 11776, 60928,  7680, 56832,
 670      8448, 57600,  4352, 53504, 11520, 60672,  7424, 56576 },
 671   { 41472, 25088, 37376, 20992, 44544, 28160, 40448, 24064,
 672     41216, 24832, 37120, 20736, 44288, 27904, 40192, 23808 },
 673   {  2560, 51712, 14848, 64000,  1536, 50688, 13824, 62976,
 674      2304, 51456, 14592, 63744,  1280, 50432, 13568, 62720 },
 675   { 35328, 18944, 47616, 31232, 34304, 17920, 46592, 30208,
 676     35072, 18688, 47360, 30976, 34048, 17664, 46336, 29952 },
 677   { 10752, 59904,  6656, 55808,  9728, 58880,  5632, 54784,
 678     10496, 59648,  6400, 55552,  9472, 58624,  5376, 54528 },
 679   { 43520, 27136, 39424, 23040, 42496, 26112, 38400, 22016,
 680     43264, 26880, 39168, 22784, 42240, 25856, 38144, 21760 }
 681 };
 682
 683
 684 /*
 685  * Helper function for TrueColorDither and renderXImage
 686  *
 687  * This handles the proper setting of the image data based on the image depth
 688  * and the machine's byte ordering
 689  */
 690 static void assignPixelData(unsigned int bit_depth, unsigned char **data,
 691                             unsigned long pixel) {
 692   unsigned char *pixel_data = *data;
 693   switch (bit_depth) {
 694   case  8: //  8bpp
 695     pixel_data[0] = pixel;
 696     ++pixel_data;
 697     break;
 698
 699   case 16: // 16bpp LSB
 700     pixel_data[0] = pixel;
 701     pixel_data[1] = pixel >> 8;
 702     pixel_data += 2;
 703     break;
 704
 705   case 17: // 16bpp MSB
 706     pixel_data[0] = pixel >> 8;
 707     pixel_data[1] = pixel;
 708     pixel_data += 2;
 709     break;
 710
 711   case 24: // 24bpp LSB
 712     pixel_data[0] = pixel;
 713     pixel_data[1] = pixel >> 8;
 714     pixel_data[2] = pixel >> 16;
 715     pixel_data += 3;
 716     break;
 717
 718   case 25: // 24bpp MSB
 719     pixel_data[0] = pixel >> 16;
 720     pixel_data[1] = pixel >> 8;
 721     pixel_data[2] = pixel;
 722     pixel_data += 3;
 723     break;
 724
 725   case 32: // 32bpp LSB
 726     pixel_data[0] = pixel;
 727     pixel_data[1] = pixel >> 8;
 728     pixel_data[2] = pixel >> 16;
 729     pixel_data[3] = pixel >> 24;
 730     pixel_data += 4;
 731     break;
 732
 733   case 33: // 32bpp MSB
 734     pixel_data[0] = pixel >> 24;
 735     pixel_data[1] = pixel >> 16;
 736     pixel_data[2] = pixel >> 8;
 737     pixel_data[3] = pixel;
 738     pixel_data += 4;
 739     break;
 740   }
 741   *data = pixel_data; // assign back so we don't lose our place
 742 }
 743
 744
 745 // algorithm: ordered dithering... many many thanks to rasterman
 746 // (raster@rasterman.com) for telling me about this... portions of this
 747 // code is based off of his code in Imlib
 748 void bt::Image::OrderedDither(XColorTable *colortable,
 749                               unsigned int bit_depth,
 750                               unsigned int bytes_per_line,
 751                               unsigned char *pixel_data) {
 752   unsigned int x, y, dithx, dithy, r, g, b, error, offset;
 753   unsigned char *ppixel_data = pixel_data;
 754
 755   unsigned int maxr = 255, maxg = 255, maxb = 255;
 756   colortable->map(maxr, maxg, maxb);
 757
 758   for (y = 0, offset = 0; y < height; ++y) {
 759     dithy = y & 15;
 760
 761     for (x = 0; x < width; ++x, ++offset) {
 762       dithx = x & 15;
 763
 764       error = dither16[dithy][dithx];
 765
 766       r = (((256 * maxr + maxr + 1) * data[offset].red   + error) / 65536);
 767       g = (((256 * maxg + maxg + 1) * data[offset].green + error) / 65536);
 768       b = (((256 * maxb + maxb + 1) * data[offset].blue  + error) / 65536);
 769
 770       assignPixelData(bit_depth, &pixel_data, colortable->pixel(r, g, b));
 771     }
 772
 773     pixel_data = (ppixel_data += bytes_per_line);
 774   }
 775 }
 776
 777
 778 void bt::Image::FloydSteinbergDither(XColorTable *colortable,
 779                                      unsigned int bit_depth,
 780                                      unsigned int bytes_per_line,
 781                                      unsigned char *pixel_data) {
 782   int * const error = new int[width * 6];
 783   int * const r_line1 = error + (width * 0);
 784   int * const g_line1 = error + (width * 1);
 785   int * const b_line1 = error + (width * 2);
 786   int * const r_line2 = error + (width * 3);
 787   int * const g_line2 = error + (width * 4);
 788   int * const b_line2 = error + (width * 5);
 789
 790   int rer, ger, ber;
 791   unsigned int x, y, r, g, b, offset;
 792   unsigned char *ppixel_data = pixel_data;
 793   RGB *pixels = new RGB[width];
 794
 795   unsigned int maxr = 255, maxg = 255, maxb = 255;
 796   colortable->map(maxr, maxg, maxb);
 797   maxr = 255u / maxr;
 798   maxg = 255u / maxg;
 799   maxb = 255u / maxb;
 800
 801   for (y = 0, offset = 0; y < height; ++y) {
 802     const bool reverse = bool(y & 1);
 803
 804     int * const rl1 = (reverse) ? r_line2 : r_line1;
 805     int * const gl1 = (reverse) ? g_line2 : g_line1;
 806     int * const bl1 = (reverse) ? b_line2 : b_line1;
 807     int * const rl2 = (reverse) ? r_line1 : r_line2;
 808     int * const gl2 = (reverse) ? g_line1 : g_line2;
 809     int * const bl2 = (reverse) ? b_line1 : b_line2;
 810
 811     if (y == 0) {
 812       for (x = 0; x < width; ++x) {
 813         rl1[x] = static_cast<int>(data[x].red);
 814         gl1[x] = static_cast<int>(data[x].green);
 815         bl1[x] = static_cast<int>(data[x].blue);
 816       }
 817     }
 818     if (y+1 < height) {
 819       for (x = 0; x < width; ++x) {
 820         rl2[x] = static_cast<int>(data[offset + width + x].red);
 821         gl2[x] = static_cast<int>(data[offset + width + x].green);
 822         bl2[x] = static_cast<int>(data[offset + width + x].blue);
 823       }
 824     }
 825
 826     // bi-directional dither
 827     if (reverse) {
 828       for (x = 0; x < width; ++x) {
 829         r = static_cast<unsigned int>(std::max(std::min(rl1[x], 255), 0));
 830         g = static_cast<unsigned int>(std::max(std::min(gl1[x], 255), 0));
 831         b = static_cast<unsigned int>(std::max(std::min(bl1[x], 255), 0));
 832
 833         colortable->map(r, g, b);
 834
 835         pixels[x].red   = r;
 836         pixels[x].green = g;
 837         pixels[x].blue  = b;
 838
 839         rer = rl1[x] - static_cast<int>(r * maxr);
 840         ger = gl1[x] - static_cast<int>(g * maxg);
 841         ber = bl1[x] - static_cast<int>(b * maxb);
 842
 843         if (x+1 < width) {
 844           rl1[x+1] += rer * 7 / 16;
 845           gl1[x+1] += ger * 7 / 16;
 846           bl1[x+1] += ber * 7 / 16;
 847           rl2[x+1] += rer * 1 / 16;
 848           gl2[x+1] += ger * 1 / 16;
 849           bl2[x+1] += ber * 1 / 16;
 850         }
 851         rl2[x] += rer * 5 / 16;
 852         gl2[x] += ger * 5 / 16;
 853         bl2[x] += ber * 5 / 16;
 854         if (x > 0) {
 855           rl2[x-1] += rer * 3 / 16;
 856           gl2[x-1] += ger * 3 / 16;
 857           bl2[x-1] += ber * 3 / 16;
 858         }
 859       }
 860     } else {
 861       for (x = width; x-- > 0; ) {
 862         r = static_cast<unsigned int>(std::max(std::min(rl1[x], 255), 0));
 863         g = static_cast<unsigned int>(std::max(std::min(gl1[x], 255), 0));
 864         b = static_cast<unsigned int>(std::max(std::min(bl1[x], 255), 0));
 865
 866         colortable->map(r, g, b);
 867
 868         pixels[x].red   = r;
 869         pixels[x].green = g;
 870         pixels[x].blue  = b;
 871
 872         rer = rl1[x] - static_cast<int>(r * maxr);
 873         ger = gl1[x] - static_cast<int>(g * maxg);
 874         ber = bl1[x] - static_cast<int>(b * maxb);
 875
 876         if (x > 0) {
 877           rl1[x-1] += rer * 7 / 16;
 878           gl1[x-1] += ger * 7 / 16;
 879           bl1[x-1] += ber * 7 / 16;
 880           rl2[x-1] += rer * 1 / 16;
 881           gl2[x-1] += ger * 1 / 16;
 882           bl2[x-1] += ber * 1 / 16;
 883         }
 884         rl2[x] += rer * 5 / 16;
 885         gl2[x] += ger * 5 / 16;
 886         bl2[x] += ber * 5 / 16;
 887         if (x+1 < width) {
 888           rl2[x+1] += rer * 3 / 16;
 889           gl2[x+1] += ger * 3 / 16;
 890           bl2[x+1] += ber * 3 / 16;
 891         }
 892       }
 893     }
 894     for (x = 0; x < width; ++x) {
 895       r = pixels[x].red;
 896       g = pixels[x].green;
 897       b = pixels[x].blue;
 898       assignPixelData(bit_depth, &pixel_data, colortable->pixel(r, g, b));
 899     }
 900
 901     offset += width;
 902     pixel_data = (ppixel_data += bytes_per_line);
 903   }
 904
 905   delete [] error;
 906   delete [] pixels;
 907 }
 908
 909
 910 Pixmap bt::Image::renderPixmap(const Display &display, unsigned int screen) {
 911   // get the colortable for the screen. if necessary, we will create one.
 912   if (colorTableList.empty())
 913     colorTableList.resize(display.screenCount(), 0);
 914
 915   if (!colorTableList[screen])
 916     colorTableList[screen] = new XColorTable(display, screen, maximumColors());
 917
 918   XColorTable *colortable = colorTableList[screen];
 919   const ScreenInfo &screeninfo = display.screenInfo(screen);
 920   XImage *image = 0;
 921   bool shm_ok = false;
 922
 923 #ifdef MITSHM
 924   // try to use MIT-SHM extension
 925   if (use_shm) {
 926     image = createShmImage(display, screeninfo, width, height);
 927     shm_ok = (image != 0);
 928   }
 929 #endif // MITSHM
 930
 931   if (!shm_ok) {
 932     // regular XImage
 933     image = XCreateImage(display.XDisplay(), screeninfo.visual(),
 934                          screeninfo.depth(), ZPixmap,
 935                          0, 0, width, height, 32, 0);
 936     if (!image)
 937       return None;
 938
 939     buffer.reserve(image->bytes_per_line * (height + 1));
 940     image->data = reinterpret_cast<char *>(&buffer[0]);
 941   }
 942
 943   unsigned char *d = reinterpret_cast<unsigned char *>(image->data);
 944   unsigned int o = image->bits_per_pixel
 945                    + ((image->byte_order == MSBFirst) ? 1 : 0);
 946
 947   DitherMode dmode =
 948     (width > 1 && height > 1) ? colortable->ditherMode() : NoDither;
 949
 950   // render to XImage
 951   switch (dmode) {
 952   case bt::FloydSteinbergDither:
 953     FloydSteinbergDither(colortable, o, image->bytes_per_line, d);
 954     break;
 955
 956   case bt::OrderedDither:
 957     OrderedDither(colortable, o, image->bytes_per_line, d);
 958     break;
 959
 960   case bt::NoDither: {
 961     unsigned int x, y, offset, r, g, b;
 962     unsigned char *pixel_data = d, *ppixel_data = d;
 963
 964     for (y = 0, offset = 0; y < height; ++y) {
 965       for (x = 0; x < width; ++x, ++offset) {
 966         r = data[offset].red;
 967         g = data[offset].green;
 968         b = data[offset].blue;
 969
 970         colortable->map(r, g, b);
 971         assignPixelData(o, &pixel_data, colortable->pixel(r, g, b));
 972       }
 973
 974       pixel_data = (ppixel_data += image->bytes_per_line);
 975     }
 976     break;
 977   }
 978   } // switch dmode
 979
 980   Pixmap pixmap = XCreatePixmap(display.XDisplay(), screeninfo.rootWindow(),
 981                                 width, height, screeninfo.depth());
 982   if (pixmap == None) {
 983     image->data = 0;
 984     XDestroyImage(image);
 985
 986     return None;
 987   }
 988
 989   Pen pen(screen, Color(0, 0, 0));
 990
 991 #ifdef MITSHM
 992   if (shm_ok) {
 993     // use MIT-SHM extension
 994     XShmPutImage(pen.XDisplay(), pixmap, pen.gc(), image,
 995                  0, 0, 0, 0, width, height, False);
 996
 997     destroyShmImage(display, image);
 998   } else
 999 #endif // MITSHM
1000     {
1001       // normal XPutImage
1002       XPutImage(pen.XDisplay(), pixmap, pen.gc(), image,
1003                 0, 0, 0, 0, width, height);
1004
1005       image->data = 0;
1006       XDestroyImage(image);
1007     }
1008
1009   return pixmap;
1010 }
1011
1012
1013 void bt::Image::bevel(unsigned int border_width) {
1014   if (width <= 2 || height <= 2 ||
1015       width <= (border_width * 4) || height <= (border_width * 4))
1016     return;
1017
1018   RGB *p = data + (border_width * width) + border_width;
1019   unsigned int w = width - (border_width * 2);
1020   unsigned int h = height - (border_width * 2) - 2;
1021   unsigned char rr, gg, bb;
1022
1023   // top of the bevel
1024   do {
1025     rr = p->red   + (p->red   >> 1);
1026     gg = p->green + (p->green >> 1);
1027     bb = p->blue  + (p->blue  >> 1);
1028
1029     if (rr < p->red  )
1030       rr = ~0;
1031     if (gg < p->green)
1032       gg = ~0;
1033     if (bb < p->blue )
1034       bb = ~0;
1035
1036     p->red = rr;
1037     p->green = gg;
1038     p->blue = bb;
1039
1040     ++p;
1041   } while (--w);
1042
1043   p += border_width + border_width;
1044   w = width - (border_width * 2);
1045
1046   // left and right of the bevel
1047   do {
1048     rr = p->red   + (p->red   >> 1);
1049     gg = p->green + (p->green >> 1);
1050     bb = p->blue  + (p->blue  >> 1);
1051
1052     if (rr < p->red)
1053       rr = ~0;
1054     if (gg < p->green)
1055       gg = ~0;
1056     if (bb < p->blue)
1057       bb = ~0;
1058
1059     p->red = rr;
1060     p->green = gg;
1061     p->blue = bb;
1062
1063     p += w - 1;
1064
1065     rr = (p->red   >> 2) + (p->red   >> 1);
1066     gg = (p->green >> 2) + (p->green >> 1);
1067     bb = (p->blue  >> 2) + (p->blue  >> 1);
1068
1069     if (rr > p->red  )
1070       rr = 0;
1071     if (gg > p->green)
1072       gg = 0;
1073     if (bb > p->blue )
1074       bb = 0;
1075
1076     p->red   = rr;
1077     p->green = gg;
1078     p->blue  = bb;
1079
1080     p += border_width + border_width + 1;
1081   } while (--h);
1082
1083   w = width - (border_width * 2);
1084
1085   // bottom of the bevel
1086   do {
1087     rr = (p->red   >> 2) + (p->red   >> 1);
1088     gg = (p->green >> 2) + (p->green >> 1);
1089     bb = (p->blue  >> 2) + (p->blue  >> 1);
1090
1091     if (rr > p->red  )
1092       rr = 0;
1093     if (gg > p->green)
1094       gg = 0;
1095     if (bb > p->blue )
1096       bb = 0;
1097
1098     p->red   = rr;
1099     p->green = gg;
1100     p->blue  = bb;
1101
1102     ++p;
1103   } while (--w);
1104 }
1105
1106
1107 void bt::Image::dgradient(const Color &from, const Color &to,
1108                           bool interlaced) {
1109   // diagonal gradient code was written by Mike Cole <mike@mydot.com>
1110   // modified for interlacing by Brad Hughes
1111
1112   double drx, dgx, dbx, dry, dgy, dby;
1113   double yr = 0.0, yg = 0.0, yb = 0.0,
1114          xr = static_cast<double>(from.red()),
1115          xg = static_cast<double>(from.green()),
1116          xb = static_cast<double>(from.blue());
1117
1118   RGB *p = data;
1119   unsigned int w = width * 2, h = height * 2;
1120   unsigned int x, y;
1121
1122   const unsigned int dimension = std::max(width, height);
1123   unsigned int *alloc = new unsigned int[dimension * 6];
1124   unsigned int *xt[3], *yt[3];
1125   xt[0] = alloc + (dimension * 0);
1126   xt[1] = alloc + (dimension * 1);
1127   xt[2] = alloc + (dimension * 2);
1128   yt[0] = alloc + (dimension * 3);
1129   yt[1] = alloc + (dimension * 4);
1130   yt[2] = alloc + (dimension * 5);
1131
1132   dry = drx = static_cast<double>(to.red()   - from.red());
1133   dgy = dgx = static_cast<double>(to.green() - from.green());
1134   dby = dbx = static_cast<double>(to.blue()  - from.blue());
1135
1136   // Create X table
1137   drx /= w;
1138   dgx /= w;
1139   dbx /= w;
1140
1141   for (x = 0; x < width; ++x) {
1142     xt[0][x] = static_cast<unsigned char>(xr);
1143     xt[1][x] = static_cast<unsigned char>(xg);
1144     xt[2][x] = static_cast<unsigned char>(xb);
1145
1146     xr += drx;
1147     xg += dgx;
1148     xb += dbx;
1149   }
1150
1151   // Create Y table
1152   dry /= h;
1153   dgy /= h;
1154   dby /= h;
1155
1156   for (y = 0; y < height; ++y) {
1157     yt[0][y] = static_cast<unsigned char>(yr);
1158     yt[1][y] = static_cast<unsigned char>(yg);
1159     yt[2][y] = static_cast<unsigned char>(yb);
1160
1161     yr += dry;
1162     yg += dgy;
1163     yb += dby;
1164   }
1165
1166   // Combine tables to create gradient
1167
1168   if (!interlaced) {
1169     // normal dgradient
1170     for (y = 0; y < height; ++y) {
1171       for (x = 0; x < width; ++x, ++p) {
1172         p->red   = xt[0][x] + yt[0][y];
1173         p->green = xt[1][x] + yt[1][y];
1174         p->blue  = xt[2][x] + yt[2][y];
1175       }
1176     }
1177   } else {
1178     // interlacing effect
1179     for (y = 0; y < height; ++y) {
1180       for (x = 0; x < width; ++x, ++p) {
1181         p->red   = xt[0][x] + yt[0][y];
1182         p->green = xt[1][x] + yt[1][y];
1183         p->blue  = xt[2][x] + yt[2][y];
1184
1185         if (y & 1) {
1186           p->red   = (p->red   >> 1) + (p->red   >> 2);
1187           p->green = (p->green >> 1) + (p->green >> 2);
1188           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1189         }
1190       }
1191     }
1192   }
1193
1194   delete [] alloc;
1195 }
1196
1197
1198 void bt::Image::hgradient(const Color &from, const Color &to,
1199                           bool interlaced) {
1200   double drx, dgx, dbx,
1201     xr = static_cast<double>(from.red()),
1202     xg = static_cast<double>(from.green()),
1203     xb = static_cast<double>(from.blue());
1204   RGB *p = data;
1205   unsigned int total = width * (height - 2);
1206   unsigned int x;
1207
1208   drx = static_cast<double>(to.red()   - from.red());
1209   dgx = static_cast<double>(to.green() - from.green());
1210   dbx = static_cast<double>(to.blue()  - from.blue());
1211
1212   drx /= width;
1213   dgx /= width;
1214   dbx /= width;
1215
1216   if (interlaced && height > 1) {
1217     // interlacing effect
1218
1219     // first line
1220     for (x = 0; x < width; ++x, ++p) {
1221       p->red   = static_cast<unsigned char>(xr);
1222       p->green = static_cast<unsigned char>(xg);
1223       p->blue  = static_cast<unsigned char>(xb);
1224
1225       xr += drx;
1226       xg += dgx;
1227       xb += dbx;
1228     }
1229
1230     // second line
1231     xr = static_cast<double>(from.red()),
1232     xg = static_cast<double>(from.green()),
1233     xb = static_cast<double>(from.blue());
1234
1235     for (x = 0; x < width; ++x, ++p) {
1236       p->red   = static_cast<unsigned char>(xr);
1237       p->green = static_cast<unsigned char>(xg);
1238       p->blue  = static_cast<unsigned char>(xb);
1239
1240       p->red   = (p->red   >> 1) + (p->red   >> 2);
1241       p->green = (p->green >> 1) + (p->green >> 2);
1242       p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1243
1244       xr += drx;
1245       xg += dgx;
1246       xb += dbx;
1247     }
1248   } else {
1249     // first line
1250     for (x = 0; x < width; ++x, ++p) {
1251       p->red   = static_cast<unsigned char>(xr);
1252       p->green = static_cast<unsigned char>(xg);
1253       p->blue  = static_cast<unsigned char>(xb);
1254
1255       xr += drx;
1256       xg += dgx;
1257       xb += dbx;
1258     }
1259
1260     if (height > 1) {
1261       // second line
1262       memcpy(p, data, width * sizeof(RGB));
1263       p += width;
1264     }
1265   }
1266
1267   // rest of the gradient
1268   for (x = 0; x < total; ++x)
1269     p[x] = data[x];
1270 }
1271
1272
1273 void bt::Image::vgradient(const Color &from, const Color &to,
1274                           bool interlaced) {
1275   double dry, dgy, dby,
1276     yr = static_cast<double>(from.red()  ),
1277     yg = static_cast<double>(from.green()),
1278     yb = static_cast<double>(from.blue() );
1279   RGB *p = data;
1280   unsigned int x, y;
1281
1282   dry = static_cast<double>(to.red()   - from.red()  );
1283   dgy = static_cast<double>(to.green() - from.green());
1284   dby = static_cast<double>(to.blue()  - from.blue() );
1285
1286   dry /= height;
1287   dgy /= height;
1288   dby /= height;
1289
1290   if (interlaced) {
1291     // faked interlacing effect
1292     for (y = 0; y < height; ++y) {
1293       const RGB rgb = {
1294         static_cast<unsigned char>((y & 1) ? (yr * 3. / 4.) : yr),
1295         static_cast<unsigned char>((y & 1) ? (yg * 3. / 4.) : yg),
1296         static_cast<unsigned char>((y & 1) ? (yb * 3. / 4.) : yb),
1297         0
1298       };
1299       for (x = 0; x < width; ++x, ++p)
1300         *p = rgb;
1301
1302       yr += dry;
1303       yg += dgy;
1304       yb += dby;
1305     }
1306   } else {
1307     // normal vgradient
1308     for (y = 0; y < height; ++y) {
1309       const RGB rgb = {
1310         static_cast<unsigned char>(yr),
1311         static_cast<unsigned char>(yg),
1312         static_cast<unsigned char>(yb),
1313         0
1314       };
1315       for (x = 0; x < width; ++x, ++p)
1316         *p = rgb;
1317
1318       yr += dry;
1319       yg += dgy;
1320       yb += dby;
1321     }
1322   }
1323 }
1324
1325
1326 void bt::Image::pgradient(const Color &from, const Color &to,
1327                           bool interlaced) {
1328   // pyramid gradient -  based on original dgradient, written by
1329   // Mosfet (mosfet@kde.org)
1330   // adapted from kde sources for Blackbox by Brad Hughes
1331
1332   double yr, yg, yb, drx, dgx, dbx, dry, dgy, dby, xr, xg, xb;
1333   int rsign, gsign, bsign;
1334   RGB *p = data;
1335   unsigned int tr = to.red(), tg = to.green(), tb = to.blue();
1336   unsigned int x, y;
1337
1338   const unsigned int dimension = std::max(width, height);
1339   unsigned int *alloc = new unsigned int[dimension * 6];
1340   unsigned int *xt[3], *yt[3];
1341   xt[0] = alloc + (dimension * 0);
1342   xt[1] = alloc + (dimension * 1);
1343   xt[2] = alloc + (dimension * 2);
1344   yt[0] = alloc + (dimension * 3);
1345   yt[1] = alloc + (dimension * 4);
1346   yt[2] = alloc + (dimension * 5);
1347
1348   dry = drx = static_cast<double>(to.red()   - from.red());
1349   dgy = dgx = static_cast<double>(to.green() - from.green());
1350   dby = dbx = static_cast<double>(to.blue()  - from.blue());
1351
1352   rsign = (drx < 0) ? -1 : 1;
1353   gsign = (dgx < 0) ? -1 : 1;
1354   bsign = (dbx < 0) ? -1 : 1;
1355
1356   xr = yr = (drx / 2);
1357   xg = yg = (dgx / 2);
1358   xb = yb = (dbx / 2);
1359
1360   // Create X table
1361   drx /= width;
1362   dgx /= width;
1363   dbx /= width;
1364
1365   for (x = 0; x < width; ++x) {
1366     xt[0][x] = static_cast<unsigned char>(fabs(xr));
1367     xt[1][x] = static_cast<unsigned char>(fabs(xg));
1368     xt[2][x] = static_cast<unsigned char>(fabs(xb));
1369
1370     xr -= drx;
1371     xg -= dgx;
1372     xb -= dbx;
1373   }
1374
1375   // Create Y table
1376   dry /= height;
1377   dgy /= height;
1378   dby /= height;
1379
1380   for (y = 0; y < height; ++y) {
1381     yt[0][y] = static_cast<unsigned char>(fabs(yr));
1382     yt[1][y] = static_cast<unsigned char>(fabs(yg));
1383     yt[2][y] = static_cast<unsigned char>(fabs(yb));
1384
1385     yr -= dry;
1386     yg -= dgy;
1387     yb -= dby;
1388   }
1389
1390   // Combine tables to create gradient
1391
1392   if (!interlaced) {
1393     // normal pgradient
1394     for (y = 0; y < height; ++y) {
1395       for (x = 0; x < width; ++x, ++p) {
1396         p->red =
1397           static_cast<unsigned char>(tr - (rsign * (xt[0][x] + yt[0][y])));
1398         p->green =
1399           static_cast<unsigned char>(tg - (gsign * (xt[1][x] + yt[1][y])));
1400         p->blue =
1401           static_cast<unsigned char>(tb - (bsign * (xt[2][x] + yt[2][y])));
1402       }
1403     }
1404   } else {
1405     // interlacing effect
1406     for (y = 0; y < height; ++y) {
1407       for (x = 0; x < width; ++x, ++p) {
1408         p->red =
1409           static_cast<unsigned char>(tr - (rsign * (xt[0][x] + yt[0][y])));
1410         p->green =
1411           static_cast<unsigned char>(tg - (gsign * (xt[1][x] + yt[1][y])));
1412         p->blue =
1413           static_cast<unsigned char>(tb - (bsign * (xt[2][x] + yt[2][y])));
1414
1415         if (y & 1) {
1416           p->red   = (p->red   >> 1) + (p->red   >> 2);
1417           p->green = (p->green >> 1) + (p->green >> 2);
1418           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1419         }
1420       }
1421     }
1422   }
1423
1424   delete [] alloc;
1425 }
1426
1427
1428 void bt::Image::rgradient(const Color &from, const Color &to,
1429                           bool interlaced) {
1430   // rectangle gradient -  based on original dgradient, written by
1431   // Mosfet (mosfet@kde.org)
1432   // adapted from kde sources for Blackbox by Brad Hughes
1433
1434   double drx, dgx, dbx, dry, dgy, dby, xr, xg, xb, yr, yg, yb;
1435   int rsign, gsign, bsign;
1436   RGB *p = data;
1437   unsigned int tr = to.red(), tg = to.green(), tb = to.blue();
1438   unsigned int x, y;
1439
1440   const unsigned int dimension = std::max(width, height);
1441   unsigned int *alloc = new unsigned int[dimension * 6];
1442   unsigned int *xt[3], *yt[3];
1443   xt[0] = alloc + (dimension * 0);
1444   xt[1] = alloc + (dimension * 1);
1445   xt[2] = alloc + (dimension * 2);
1446   yt[0] = alloc + (dimension * 3);
1447   yt[1] = alloc + (dimension * 4);
1448   yt[2] = alloc + (dimension * 5);
1449
1450   dry = drx = static_cast<double>(to.red()   - from.red());
1451   dgy = dgx = static_cast<double>(to.green() - from.green());
1452   dby = dbx = static_cast<double>(to.blue()  - from.blue());
1453
1454   rsign = (drx < 0) ? -2 : 2;
1455   gsign = (dgx < 0) ? -2 : 2;
1456   bsign = (dbx < 0) ? -2 : 2;
1457
1458   xr = yr = (drx / 2);
1459   xg = yg = (dgx / 2);
1460   xb = yb = (dbx / 2);
1461
1462   // Create X table
1463   drx /= width;
1464   dgx /= width;
1465   dbx /= width;
1466
1467   for (x = 0; x < width; ++x) {
1468     xt[0][x] = static_cast<unsigned char>(fabs(xr));
1469     xt[1][x] = static_cast<unsigned char>(fabs(xg));
1470     xt[2][x] = static_cast<unsigned char>(fabs(xb));
1471
1472     xr -= drx;
1473     xg -= dgx;
1474     xb -= dbx;
1475   }
1476
1477   // Create Y table
1478   dry /= height;
1479   dgy /= height;
1480   dby /= height;
1481
1482   for (y = 0; y < height; ++y) {
1483     yt[0][y] = static_cast<unsigned char>(fabs(yr));
1484     yt[1][y] = static_cast<unsigned char>(fabs(yg));
1485     yt[2][y] = static_cast<unsigned char>(fabs(yb));
1486
1487     yr -= dry;
1488     yg -= dgy;
1489     yb -= dby;
1490   }
1491
1492   // Combine tables to create gradient
1493
1494   if (!interlaced) {
1495     // normal rgradient
1496     for (y = 0; y < height; ++y) {
1497       for (x = 0; x < width; ++x, ++p) {
1498         p->red =
1499           static_cast<unsigned char>(tr - (rsign *
1500                                            std::max(xt[0][x], yt[0][y])));
1501         p->green =
1502           static_cast<unsigned char>(tg - (gsign *
1503                                            std::max(xt[1][x], yt[1][y])));
1504         p->blue =
1505           static_cast<unsigned char>(tb - (bsign *
1506                                            std::max(xt[2][x], yt[2][y])));
1507       }
1508     }
1509   } else {
1510     // interlacing effect
1511     for (y = 0; y < height; ++y) {
1512       for (x = 0; x < width; ++x, ++p) {
1513         p->red =
1514           static_cast<unsigned char>(tr - (rsign *
1515                                            std::max(xt[0][x], yt[0][y])));
1516         p->green =
1517           static_cast<unsigned char>(tg - (gsign *
1518                                            std::max(xt[1][x], yt[1][y])));
1519         p->blue =
1520           static_cast<unsigned char>(tb - (bsign *
1521                                            std::max(xt[2][x], yt[2][y])));
1522
1523         if (y & 1) {
1524           p->red   = (p->red   >> 1) + (p->red   >> 2);
1525           p->green = (p->green >> 1) + (p->green >> 2);
1526           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1527         }
1528       }
1529     }
1530   }
1531
1532   delete [] alloc;
1533 }
1534
1535
1536 void bt::Image::egradient(const Color &from, const Color &to,
1537                           bool interlaced) {
1538   // elliptic gradient -  based on original dgradient, written by
1539   // Mosfet (mosfet@kde.org)
1540   // adapted from kde sources for Blackbox by Brad Hughes
1541
1542   double drx, dgx, dbx, dry, dgy, dby, yr, yg, yb, xr, xg, xb;
1543   int rsign, gsign, bsign;
1544   RGB *p = data;
1545   unsigned int tr = to.red(), tg = to.green(), tb = to.blue();
1546   unsigned int x, y;
1547
1548   const unsigned int dimension = std::max(width, height);
1549   unsigned int *alloc = new unsigned int[dimension * 6];
1550   unsigned int *xt[3], *yt[3];
1551   xt[0] = alloc + (dimension * 0);
1552   xt[1] = alloc + (dimension * 1);
1553   xt[2] = alloc + (dimension * 2);
1554   yt[0] = alloc + (dimension * 3);
1555   yt[1] = alloc + (dimension * 4);
1556   yt[2] = alloc + (dimension * 5);
1557
1558   dry = drx = static_cast<double>(to.red() - from.red());
1559   dgy = dgx = static_cast<double>(to.green() - from.green());
1560   dby = dbx = static_cast<double>(to.blue() - from.blue());
1561
1562   rsign = (drx < 0) ? -1 : 1;
1563   gsign = (dgx < 0) ? -1 : 1;
1564   bsign = (dbx < 0) ? -1 : 1;
1565
1566   xr = yr = (drx / 2);
1567   xg = yg = (dgx / 2);
1568   xb = yb = (dbx / 2);
1569
1570   // Create X table
1571   drx /= width;
1572   dgx /= width;
1573   dbx /= width;
1574
1575   for (x = 0; x < width; x++) {
1576     xt[0][x] = static_cast<unsigned int>(xr * xr);
1577     xt[1][x] = static_cast<unsigned int>(xg * xg);
1578     xt[2][x] = static_cast<unsigned int>(xb * xb);
1579
1580     xr -= drx;
1581     xg -= dgx;
1582     xb -= dbx;
1583   }
1584
1585   // Create Y table
1586   dry /= height;
1587   dgy /= height;
1588   dby /= height;
1589
1590   for (y = 0; y < height; y++) {
1591     yt[0][y] = static_cast<unsigned int>(yr * yr);
1592     yt[1][y] = static_cast<unsigned int>(yg * yg);
1593     yt[2][y] = static_cast<unsigned int>(yb * yb);
1594
1595     yr -= dry;
1596     yg -= dgy;
1597     yb -= dby;
1598   }
1599
1600   // Combine tables to create gradient
1601
1602   if (!interlaced) {
1603     // normal egradient
1604     for (y = 0; y < height; ++y) {
1605       for (x = 0; x < width; ++x, ++p) {
1606         p->red   = static_cast<unsigned char>
1607                    (tr - (rsign * static_cast<int>(sqrt(xt[0][x] +
1608                                                         yt[0][y]))));
1609         p->green = static_cast<unsigned char>
1610                    (tg - (gsign * static_cast<int>(sqrt(xt[1][x] +
1611                                                         yt[1][y]))));
1612         p->blue  = static_cast<unsigned char>
1613                    (tb - (bsign * static_cast<int>(sqrt(xt[2][x] +
1614                                                         yt[2][y]))));
1615       }
1616     }
1617   } else {
1618     // interlacing effect
1619     for (y = 0; y < height; ++y) {
1620       for (x = 0; x < width; ++x, ++p) {
1621         p->red   = static_cast<unsigned char>
1622                    (tr - (rsign * static_cast<int>(sqrt(xt[0][x]
1623                                                         + yt[0][y]))));
1624         p->green = static_cast<unsigned char>
1625                    (tg - (gsign * static_cast<int>(sqrt(xt[1][x]
1626                                                         + yt[1][y]))));
1627         p->blue  = static_cast<unsigned char>
1628                    (tb - (bsign * static_cast<int>(sqrt(xt[2][x]
1629                                                         + yt[2][y]))));
1630
1631         if (y & 1) {
1632           p->red   = (p->red   >> 1) + (p->red   >> 2);
1633           p->green = (p->green >> 1) + (p->green >> 2);
1634           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1635         }
1636       }
1637     }
1638   }
1639
1640   delete [] alloc;
1641 }
1642
1643
1644 void bt::Image::pcgradient(const Color &from, const Color &to,
1645                            bool interlaced) {
1646   // pipe cross gradient -  based on original dgradient, written by
1647   // Mosfet (mosfet@kde.org)
1648   // adapted from kde sources for Blackbox by Brad Hughes
1649
1650   double drx, dgx, dbx, dry, dgy, dby, xr, xg, xb, yr, yg, yb;
1651   int rsign, gsign, bsign;
1652   RGB *p = data;
1653   unsigned int tr = to.red(), tg = to.green(), tb = to.blue();
1654   unsigned int x, y;
1655
1656   const unsigned int dimension = std::max(width, height);
1657   unsigned int *alloc = new unsigned int[dimension * 6];
1658   unsigned int *xt[3], *yt[3];
1659   xt[0] = alloc + (dimension * 0);
1660   xt[1] = alloc + (dimension * 1);
1661   xt[2] = alloc + (dimension * 2);
1662   yt[0] = alloc + (dimension * 3);
1663   yt[1] = alloc + (dimension * 4);
1664   yt[2] = alloc + (dimension * 5);
1665
1666   dry = drx = static_cast<double>(to.red()   - from.red());
1667   dgy = dgx = static_cast<double>(to.green() - from.green());
1668   dby = dbx = static_cast<double>(to.blue()  - from.blue());
1669
1670   rsign = (drx < 0) ? -2 : 2;
1671   gsign = (dgx < 0) ? -2 : 2;
1672   bsign = (dbx < 0) ? -2 : 2;
1673
1674   xr = yr = (drx / 2);
1675   xg = yg = (dgx / 2);
1676   xb = yb = (dbx / 2);
1677
1678   // Create X table
1679   drx /= width;
1680   dgx /= width;
1681   dbx /= width;
1682
1683   for (x = 0; x < width; ++x) {
1684     xt[0][x] = static_cast<unsigned char>(fabs(xr));
1685     xt[1][x] = static_cast<unsigned char>(fabs(xg));
1686     xt[2][x] = static_cast<unsigned char>(fabs(xb));
1687
1688     xr -= drx;
1689     xg -= dgx;
1690     xb -= dbx;
1691   }
1692
1693   // Create Y table
1694   dry /= height;
1695   dgy /= height;
1696   dby /= height;
1697
1698   for (y = 0; y < height; ++y) {
1699     yt[0][y] = static_cast<unsigned char>(fabs(yr));
1700     yt[1][y] = static_cast<unsigned char>(fabs(yg));
1701     yt[2][y] = static_cast<unsigned char>(fabs(yb));
1702
1703     yr -= dry;
1704     yg -= dgy;
1705     yb -= dby;
1706   }
1707
1708   // Combine tables to create gradient
1709
1710   if (!interlaced) {
1711     // normal rgradient
1712     for (y = 0; y < height; ++y) {
1713       for (x = 0; x < width; ++x, ++p) {
1714         p->red =
1715           static_cast<unsigned char>(tr - (rsign *
1716                                            std::min(xt[0][x], yt[0][y])));
1717         p->green =
1718           static_cast<unsigned char>(tg - (gsign *
1719                                            std::min(xt[1][x], yt[1][y])));
1720         p->blue =
1721           static_cast<unsigned char>(tb - (bsign *
1722                                            std::min(xt[2][x], yt[2][y])));
1723       }
1724     }
1725   } else {
1726     // interlacing effect
1727     for (y = 0; y < height; ++y) {
1728       for (x = 0; x < width; ++x, ++p) {
1729         p->red =
1730           static_cast<unsigned char>(tr - (rsign *
1731                                            std::min(xt[0][x], yt[0][y])));
1732         p->green =
1733           static_cast<unsigned char>(tg - (gsign *
1734                                            std::min(xt[1][x], yt[1][y])));
1735         p->blue =
1736           static_cast<unsigned char>(tb - (bsign *
1737                                            std::min(xt[2][x], yt[2][y])));
1738
1739         if (y & 1) {
1740           p->red   = (p->red   >> 1) + (p->red   >> 2);
1741           p->green = (p->green >> 1) + (p->green >> 2);
1742           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1743         }
1744       }
1745     }
1746   }
1747
1748   delete [] alloc;
1749 }
1750
1751
1752 void bt::Image::cdgradient(const Color &from, const Color &to,
1753                            bool interlaced) {
1754   // cross diagonal gradient -  based on original dgradient, written by
1755   // Mosfet (mosfet@kde.org)
1756   // adapted from kde sources for Blackbox by Brad Hughes
1757
1758   double drx, dgx, dbx, dry, dgy, dby;
1759   double yr = 0.0, yg = 0.0, yb = 0.0,
1760          xr = static_cast<double>(from.red()  ),
1761          xg = static_cast<double>(from.green()),
1762          xb = static_cast<double>(from.blue() );
1763   RGB *p = data;
1764   unsigned int w = width * 2, h = height * 2;
1765   unsigned int x, y;
1766
1767   const unsigned int dimension = std::max(width, height);
1768   unsigned int *alloc = new unsigned int[dimension * 6];
1769   unsigned int *xt[3], *yt[3];
1770   xt[0] = alloc + (dimension * 0);
1771   xt[1] = alloc + (dimension * 1);
1772   xt[2] = alloc + (dimension * 2);
1773   yt[0] = alloc + (dimension * 3);
1774   yt[1] = alloc + (dimension * 4);
1775   yt[2] = alloc + (dimension * 5);
1776
1777   dry = drx = static_cast<double>(to.red()   - from.red()  );
1778   dgy = dgx = static_cast<double>(to.green() - from.green());
1779   dby = dbx = static_cast<double>(to.blue()  - from.blue() );
1780
1781   // Create X table
1782   drx /= w;
1783   dgx /= w;
1784   dbx /= w;
1785
1786   for (x = width - 1; x != 0; --x) {
1787     xt[0][x] = static_cast<unsigned char>(xr);
1788     xt[1][x] = static_cast<unsigned char>(xg);
1789     xt[2][x] = static_cast<unsigned char>(xb);
1790
1791     xr += drx;
1792     xg += dgx;
1793     xb += dbx;
1794   }
1795
1796   xt[0][x] = static_cast<unsigned char>(xr);
1797   xt[1][x] = static_cast<unsigned char>(xg);
1798   xt[2][x] = static_cast<unsigned char>(xb);
1799
1800   // Create Y table
1801   dry /= h;
1802   dgy /= h;
1803   dby /= h;
1804
1805   for (y = 0; y < height; ++y) {
1806     yt[0][y] = static_cast<unsigned char>(yr);
1807     yt[1][y] = static_cast<unsigned char>(yg);
1808     yt[2][y] = static_cast<unsigned char>(yb);
1809
1810     yr += dry;
1811     yg += dgy;
1812     yb += dby;
1813   }
1814
1815   // Combine tables to create gradient
1816
1817   if (!interlaced) {
1818     // normal dgradient
1819     for (y = 0; y < height; ++y) {
1820       for (x = 0; x < width; ++x, ++p) {
1821         p->red   = xt[0][x] + yt[0][y];
1822         p->green = xt[1][x] + yt[1][y];
1823         p->blue  = xt[2][x] + yt[2][y];
1824       }
1825     }
1826   } else {
1827     // interlacing effect
1828     for (y = 0; y < height; ++y) {
1829       for (x = 0; x < width; ++x, ++p) {
1830         p->red   = xt[0][x] + yt[0][y];
1831         p->green = xt[1][x] + yt[1][y];
1832         p->blue  = xt[2][x] + yt[2][y];
1833
1834         if (y & 1) {
1835           p->red   = (p->red   >> 1) + (p->red   >> 2);
1836           p->green = (p->green >> 1) + (p->green >> 2);
1837           p->blue  = (p->blue  >> 1) + (p->blue  >> 2);
1838         }
1839       }
1840     }
1841   }
1842
1843   delete [] alloc;
1844 }