8ff9bf106b0ef204b339a77527dafcc613934ea8
[dana/openbox.git] / obrender / image.c
1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
2
3    image.c for the Openbox window manager
4    Copyright (c) 2006        Mikael Magnusson
5    Copyright (c) 2003-2007   Dana Jansens
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    See the COPYING file for a copy of the GNU General Public License.
18 */
19
20 #include "geom.h"
21 #include "image.h"
22 #include "color.h"
23 #include "imagecache.h"
24 #ifdef USE_IMLIB2
25 #include <Imlib2.h>
26 #endif
27 #ifdef USE_LIBRSVG
28 #include <librsvg/rsvg.h>
29 #endif
30
31 #include <glib.h>
32
33 #define FRACTION        12
34 #define FLOOR(i)        ((i) & (~0UL << FRACTION))
35 #define AVERAGE(a, b)   (((((a) ^ (b)) & 0xfefefefeL) >> 1) + ((a) & (b)))
36
37 /************************************************************************
38  RrImagePic functions.
39
40  RrImagePics are pictures that are grouped together into RrImageSets.  Each
41  RrImagePic in the set has the same logical image inside it, but they are
42  of different sizes.  An RrImagePic can be an original (which comes from some
43  outside source, such as an image file), or resized from some other RrImagePic
44  to meet the needs of the user.
45 **************************************************************************/
46
47
48 /*! Set up an RrImagePic.
49   This does _not_ make a copy of the data. So the value of data must be
50   owned by the caller of this function, and not freed afterward.
51   This function does not allocate an RrImagePic, and can be used for setting
52   up a temporary RrImagePic on the stack.  Such an object would then also
53   not be freed with RrImagePicFree.
54 */
55 static void RrImagePicInit(RrImagePic *pic, gint w, gint h, RrPixel32 *data)
56 {
57     gint i;
58
59     pic->width = w;
60     pic->height = h;
61     pic->data = data;
62     pic->sum = 0;
63     for (i = w*h; i > 0; --i)
64         pic->sum += *(data++);
65 }
66
67 /*! Create a new RrImagePic from some picture data.
68   This makes a duplicate of the data.
69 */
70 static RrImagePic* RrImagePicNew(gint w, gint h, RrPixel32 *data)
71 {
72     RrImagePic *pic;
73
74     pic = g_slice_new(RrImagePic);
75     RrImagePicInit(pic, w, h, g_memdup(data, w*h*sizeof(RrPixel32)));
76     return pic;
77 }
78
79
80 /*! Destroy an RrImagePic.
81   This frees the RrImagePic object and everything inside it.
82 */
83 static void RrImagePicFree(RrImagePic *pic)
84 {
85     if (pic) {
86         g_free(pic->data);
87         g_slice_free(RrImagePic, pic);
88     }
89 }
90
91 /************************************************************************
92  RrImageSet functions.
93
94  RrImageSets hold a group of pictures, each of which represent the same logical
95  image, but are physically different sizes.
96  At any time, it may be discovered that two different RrImageSets are actually
97  holding the same logical image.  At that time, they would be merged.
98  An RrImageSet holds both original images which come from an outside source,
99  and resized images, which are generated when requests for a specific size are
100  made, and kept around in case they are request again.  There is a maximum
101  number of resized images that an RrImageSet will keep around, however.
102
103  Each RrImage points to a single RrImageSet, which keeps track of which
104  RrImages point to it.  If two RrImageSets are merged, then the RrImages which
105  pointed to the two RrImageSets will all point at the resulting merged set.
106 **************************************************************************/
107
108
109 /*! Free an RrImageSet and the stuff inside it.
110   This should only occur when there are no more RrImages pointing to the set.
111 */
112 static void RrImageSetFree(RrImageSet *self)
113 {
114     GSList *it;
115     gint i;
116
117     if (self) {
118         g_assert(self->images == NULL);
119
120         /* remove all names associated with this RrImageSet */
121         for (it = self->names; it; it = g_slist_next(it)) {
122             g_hash_table_remove(self->cache->name_table, it->data);
123             g_free(it->data);
124         }
125         g_slist_free(self->names);
126
127         /* destroy the RrImagePic objects stored in the RrImageSet.  they will
128            be keys in the cache to RrImageSet objects, so remove them from
129            the cache's pic_table as well. */
130         for (i = 0; i < self->n_original; ++i) {
131             g_hash_table_remove(self->cache->pic_table, self->original[i]);
132             RrImagePicFree(self->original[i]);
133         }
134         g_free(self->original);
135         for (i = 0; i < self->n_resized; ++i) {
136             g_hash_table_remove(self->cache->pic_table, self->resized[i]);
137             RrImagePicFree(self->resized[i]);
138         }
139         g_free(self->resized);
140
141         g_slice_free(RrImageSet, self);
142     }
143 }
144
145 /*! Remove a picture from an RrImageSet as a given position.
146    @param set The RrImageSet to remove the picture from.
147    @param i The index of the picture in the RrImageSet in the list of
148      originals (if @original is TRUE), or in the list of resized pictures (if
149      @original is FALSE).
150    @param original TRUE if the picture is an original, FALSE if it is a resized
151      version of another picture in the RrImageSet.
152  */
153 static void RrImageSetRemovePictureAt(RrImageSet *self, gint i,
154                                       gboolean original)
155 {
156     RrImagePic ***list;
157     gint *len;
158
159     if (original) {
160         list = &self->original;
161         len = &self->n_original;
162     }
163     else {
164         list = &self->resized;
165         len = &self->n_resized;
166     }
167
168     g_assert(i >= 0 && i < *len);
169
170     /* remove the picture data as a key in the cache */
171     g_hash_table_remove(self->cache->pic_table, (*list)[i]);
172
173     /* free the picture being removed */
174     RrImagePicFree((*list)[i]);
175
176     /* copy the elements after the removed one in the array forward one space
177        and shrink the array down one size */
178     for (i = i+1; i < *len; ++i)
179         (*list)[i-1] = (*list)[i];
180     --(*len);
181     *list = g_renew(RrImagePic*, *list, *len);
182 }
183
184 /*! Add an RrImagePic to an RrImageSet.
185   The RrImagePic should _not_ exist in the image cache already.
186   Pictures are added to the front of the list, to maintain the ordering of
187   newest to oldest.
188 */
189 static void RrImageSetAddPicture(RrImageSet *self, RrImagePic *pic,
190                                  gboolean original)
191 {
192     gint i;
193     RrImagePic ***list;
194     gint *len;
195
196     g_assert(pic->width > 0 && pic->height > 0);
197     g_assert(g_hash_table_lookup(self->cache->pic_table, pic) == NULL);
198
199     /* choose which list in the RrImageSet to add the new picture to. */
200     if (original) {
201         /* remove the resized picture of the same size if one exists */
202         for (i = 0; i < self->n_resized; ++i)
203             if (self->resized[i]->width == pic->width ||
204                 self->resized[i]->height == pic->height)
205             {
206                 RrImageSetRemovePictureAt(self, i, FALSE);
207                 break;
208             }
209
210         list = &self->original;
211         len = &self->n_original;
212     }
213     else {
214         list = &self->resized;
215         len = &self->n_resized;
216     }
217
218     /* grow the list by one spot, shift everything down one, and insert the new
219        picture at the front of the list */
220     *list = g_renew(RrImagePic*, *list, ++*len);
221     for (i = *len-1; i > 0; --i)
222         (*list)[i] = (*list)[i-1];
223     (*list)[0] = pic;
224
225     /* add the picture as a key to point to this image in the cache */
226     g_hash_table_insert(self->cache->pic_table, (*list)[0], self);
227
228 /*
229 #ifdef DEBUG
230     g_debug("Adding %s picture to the cache:\n    "
231             "Image 0x%lx, w %d h %d Hash %u",
232             (*list == self->original ? "ORIGINAL" : "RESIZED"),
233             (gulong)self, pic->width, pic->height, RrImagePicHash(pic));
234 #endif
235 */
236 }
237
238 /*! Merges two image sets, destroying one, and returning the other. */
239 RrImageSet* RrImageSetMergeSets(RrImageSet *b, RrImageSet *a)
240 {
241     gint a_i, b_i, merged_i;
242     RrImagePic **original, **resized;
243     gint n_original, n_resized, tmp;
244     GSList *it;
245
246     const gint max_resized = a->cache->max_resized_saved;
247
248     if (!a)
249         return b;
250     if (!b)
251         return a;
252     if (a == b)
253         return b;
254
255     /* the original and resized picture lists in an RrImageSet are kept ordered
256        as newest to oldest.  we don't have timestamps for them, so we cannot
257        preserve this in the merged RrImageSet exactly.  a decent approximation,
258        i think, is to add them in alternating order (one from a, one from b,
259        repeat).  this way, the newest from each will be near the front at
260        least, and in the resized list, when we drop an old picture, we will
261        not always only drop from a or b only, but from each of them equally (or
262        from whichever has more resized pictures.
263     */
264
265     g_assert(b->cache == a->cache);
266
267     a_i = b_i = merged_i = 0;
268     n_original = a->n_original + b->n_original;
269     original = g_new(RrImagePic*, n_original);
270     while (merged_i < n_original) {
271         if (a_i < a->n_original)
272             original[merged_i++] = a->original[a_i++];
273         if (b_i < b->n_original)
274             original[merged_i++] = b->original[b_i++];
275     }
276
277     a_i = b_i = merged_i = 0;
278     n_resized = MIN(max_resized, a->n_resized + b->n_resized);
279     resized = g_new(RrImagePic*, n_resized);
280     while (merged_i < n_resized) {
281         if (a_i < a->n_resized)
282             resized[merged_i++] = a->resized[a_i++];
283         if (b_i < b->n_resized && merged_i < n_resized)
284             resized[merged_i++] = b->resized[b_i++];
285     }
286
287     /* if there are any RrImagePic objects left over in a->resized or
288        b->resized, they need to be disposed of, and removed from the cache.
289
290        updates the size of the list, as we want to remember which pointers
291        were merged from which list (and don't want to remember the ones we
292        did not merge and have freed).
293     */
294     tmp = a_i;
295     for (; a_i < a->n_resized; ++a_i) {
296         g_hash_table_remove(a->cache->pic_table, a->resized[a_i]);
297         RrImagePicFree(a->resized[a_i]);
298     }
299     a->n_resized = tmp;
300
301     tmp = b_i;
302     for (; b_i < b->n_resized; ++b_i) {
303         g_hash_table_remove(a->cache->pic_table, b->resized[b_i]);
304         RrImagePicFree(b->resized[b_i]);
305     }
306     b->n_resized = tmp;
307
308     /* we will use the a object as the merge destination, so things in b will
309        be moving.
310
311        the cache's name_table will point to b for all the names in b->names,
312        so these need to be updated to point at a instead.
313        also, the cache's pic_table will point to b for all the pictures in b,
314        so these need to be updated to point at a as well.
315
316        any RrImage objects that were using b should now use a instead.
317
318        the names and images will be all moved into a, and the merged picture
319        lists will be placed in a.  the pictures in a and b are moved to new
320        arrays, so the arrays in a and b need to be freed explicitly (the
321        RrImageSetFree function would free the picture data too which we do not
322        want here). then b can be freed.
323     */
324
325     for (it = b->names; it; it = g_slist_next(it))
326         g_hash_table_insert(a->cache->name_table, it->data, a);
327     for (b_i = 0; b_i < b->n_original; ++b_i)
328         g_hash_table_insert(a->cache->pic_table, b->original[b_i], a);
329     for (b_i = 0; b_i < b->n_resized; ++b_i)
330         g_hash_table_insert(a->cache->pic_table, b->resized[b_i], a);
331
332     for (it = b->images; it; it = g_slist_next(it))
333         ((RrImage*)it->data)->set = a;
334
335     a->images = g_slist_concat(a->images, b->images);
336     b->images = NULL;
337     a->names = g_slist_concat(a->names, b->names);
338     b->names = NULL;
339
340     a->n_original = a->n_resized = 0;
341     g_free(a->original);
342     g_free(a->resized);
343     a->original = a->resized = NULL;
344     b->n_original = b->n_resized = 0;
345     g_free(b->original);
346     g_free(b->resized);
347     b->original = b->resized = NULL;
348
349     a->n_original = n_original;
350     a->original = original;
351     a->n_resized = n_resized;
352     a->resized = resized;
353
354     RrImageSetFree(b);
355
356     return a;
357 }
358
359 static void RrImageSetAddName(RrImageSet *set, const gchar *name)
360 {
361     gchar *n;
362
363     n = g_strdup(name);
364     set->names = g_slist_prepend(set->names, n);
365
366     /* add the new name to the hash table */
367     g_assert(g_hash_table_lookup(set->cache->name_table, n) == NULL);
368     g_hash_table_insert(set->cache->name_table, n, set);
369 }
370
371
372 /************************************************************************
373  RrImage functions.
374 **************************************************************************/
375
376
377 void RrImageRef(RrImage *self)
378 {
379     ++self->ref;
380 }
381
382 void RrImageUnref(RrImage *self)
383 {
384     if (self && --self->ref == 0) {
385         RrImageSet *set;
386 /*
387 #ifdef DEBUG
388         g_debug("Refcount to 0, removing ALL pictures from the cache:\n    "
389                 "Image 0x%lx", (gulong)self);
390 #endif
391 */
392         if (self->destroy_func)
393             self->destroy_func(self, self->destroy_data);
394
395         set = self->set;
396         set->images = g_slist_remove(set->images, self);
397
398         /* free the set as well if there are no images pointing to it */
399         if (!set->images)
400             RrImageSetFree(set);
401         g_slice_free(RrImage, self);
402     }
403 }
404
405 /*! Set function that will be called just before RrImage is destroyed. */
406 void RrImageSetDestroyFunc(RrImage *self, RrImageDestroyFunc func,
407                            gpointer data)
408 {
409     self->destroy_func = func;
410     self->destroy_data = data;
411 }
412
413 void RrImageAddFromData(RrImage *self, RrPixel32 *data, gint w, gint h)
414 {
415     RrImagePic pic, *ppic;
416     RrImageSet *set;
417
418     g_return_if_fail(self != NULL);
419     g_return_if_fail(data != NULL);
420     g_return_if_fail(w > 0 && h > 0);
421
422     RrImagePicInit(&pic, w, h, data);
423     set = g_hash_table_lookup(self->set->cache->pic_table, &pic);
424     if (set)
425         self->set = RrImageSetMergeSets(self->set, set);
426     else {
427         ppic = RrImagePicNew(w, h, data);
428         RrImageSetAddPicture(self->set, ppic, TRUE);
429     }
430 }
431
432 RrImage* RrImageNewFromData(RrImageCache *cache, RrPixel32 *data,
433                             gint w, gint h)
434 {
435     RrImagePic pic, *ppic;
436     RrImage *self;
437     RrImageSet *set;
438
439     g_return_val_if_fail(cache != NULL, NULL);
440     g_return_val_if_fail(data != NULL, NULL);
441     g_return_val_if_fail(w > 0 && h > 0, NULL);
442
443     /* finds a picture in the cache, if it is already in there, and use the
444        RrImageSet the picture lives in. */
445     RrImagePicInit(&pic, w, h, data);
446     set = g_hash_table_lookup(cache->pic_table, &pic);
447     if (set) {
448         self = set->images->data; /* just grab any RrImage from the list */
449         RrImageRef(self);
450         return self;
451     }
452
453     /* the image does not exist in any RrImageSet in the cache, so make
454        a new RrImageSet, and a new RrImage that points to it, and place the
455        new image inside the new RrImageSet */
456
457     self = g_slice_new0(RrImage);
458     self->ref = 1;
459     self->set = g_slice_new0(RrImageSet);
460     self->set->cache = cache;
461     self->set->images = g_slist_append(self->set->images, self);
462
463     ppic = RrImagePicNew(w, h, data);
464     RrImageSetAddPicture(self->set, ppic, TRUE);
465
466     return self;
467 }
468
469 #if defined(USE_IMLIB2)
470 typedef struct _ImlibLoader ImlibLoader;
471
472 struct _ImlibLoader
473 {
474     Imlib_Image img;
475 };
476
477 void DestroyImlibLoader(ImlibLoader *loader)
478 {
479     if (!loader)
480         return;
481
482     imlib_free_image();
483     g_slice_free(ImlibLoader, loader);
484 }
485
486 ImlibLoader* LoadWithImlib(gchar *path,
487                            RrPixel32 **pixel_data,
488                            gint *width,
489                            gint *height)
490 {
491     ImlibLoader *loader = g_slice_new0(ImlibLoader);
492     if (!(loader->img = imlib_load_image(path))) {
493         DestroyImlibLoader(loader);
494         return NULL;
495     }
496
497     /* Get data and dimensions of the image.
498
499        WARNING: This stuff is NOT threadsafe !!
500     */
501     imlib_context_set_image(loader->img);
502     *pixel_data = imlib_image_get_data_for_reading_only();
503     *width = imlib_image_get_width();
504     *height = imlib_image_get_height();
505
506     return loader;
507 }
508 #endif  /* USE_IMLIB2 */
509
510 #if defined(USE_LIBRSVG)
511 typedef struct _RsvgLoader RsvgLoader;
512
513 struct _RsvgLoader
514 {
515     RsvgHandle *handle;
516     cairo_surface_t *surface;
517     RrPixel32 *pixel_data;
518 };
519
520 void DestroyRsvgLoader(RsvgLoader *loader)
521 {
522     if (!loader)
523         return;
524
525     if (loader->pixel_data)
526         g_free(loader->pixel_data);
527     if (loader->surface)
528         cairo_surface_destroy(loader->surface);
529     if (loader->handle)
530         g_object_unref(loader->handle);
531     g_slice_free(RsvgLoader, loader);
532 }
533
534 RsvgLoader* LoadWithRsvg(gchar *path,
535                          RrPixel32 **pixel_data,
536                          gint *width,
537                          gint *height)
538 {
539     RsvgLoader *loader = g_slice_new0(RsvgLoader);
540
541     if (!(loader->handle = rsvg_handle_new_from_file(path, NULL))) {
542         DestroyRsvgLoader(loader);
543         return NULL;
544     }
545
546     if (!rsvg_handle_close(loader->handle, NULL)) {
547         DestroyRsvgLoader(loader);
548         return NULL;
549     }
550
551     RsvgDimensionData dimension_data;
552     rsvg_handle_get_dimensions(loader->handle, &dimension_data);
553     *width = dimension_data.width;
554     *height = dimension_data.height;
555
556     loader->surface = cairo_image_surface_create(
557         CAIRO_FORMAT_ARGB32, *width, *height);
558
559     cairo_t* context = cairo_create(loader->surface);
560     gboolean success = rsvg_handle_render_cairo(loader->handle, context);
561     cairo_destroy(context);
562
563     if (!success) {
564         DestroyRsvgLoader(loader);
565         return NULL;
566     }
567
568     loader->pixel_data = g_new(guint32, *width * *height);
569
570     /*
571       Cairo has its data in ARGB with premultiplied alpha, but RrPixel32
572       non-premultipled, so convert that. Also, RrPixel32 doesn't allow
573       strides not equal to the width of the image.
574     */
575
576     /* Verify that RrPixel32 has the same ordering as cairo. */
577     g_assert(RrDefaultAlphaOffset == 24);
578     g_assert(RrDefaultRedOffset == 16);
579     g_assert(RrDefaultGreenOffset == 8);
580     g_assert(RrDefaultBlueOffset == 0);
581
582     guint32 *out_row = loader->pixel_data;
583
584     guint32 *in_row =
585         (guint32*)cairo_image_surface_get_data(loader->surface);
586     gint in_stride = cairo_image_surface_get_stride(loader->surface);
587
588     gint y;
589     for (y = 0; y < *height; ++y) {
590         gint x;
591         for (x = 0; x < *width; ++x) {
592             guchar a = in_row[x] >> 24;
593             guchar r = (in_row[x] >> 16) & 0xff;
594             guchar g = (in_row[x] >> 8) & 0xff;
595             guchar b = in_row[x] & 0xff;
596             out_row[x] =
597                 ((r * 256 / (a + 1)) << RrDefaultRedOffset) +
598                 ((g * 256 / (a + 1)) << RrDefaultGreenOffset) +
599                 ((b * 256 / (a + 1)) << RrDefaultBlueOffset) +
600                 (a << RrDefaultAlphaOffset);
601         }
602         in_row += in_stride / 4;
603         out_row += *width;
604     }
605
606     *pixel_data = loader->pixel_data;
607
608     return loader;
609 }
610 #endif  /* USE_LIBRSVG */
611
612 RrImage* RrImageNewFromName(RrImageCache *cache, const gchar *name)
613 {
614     RrImage *self;
615     RrImageSet *set;
616     gint w, h;
617     RrPixel32 *data;
618     gchar *path;
619     gboolean loaded;
620
621 #if defined(USE_IMLIB2)
622     ImlibLoader *imlib_loader = NULL;
623 #endif
624 #if defined(USE_LIBRSVG)
625     RsvgLoader *rsvg_loader = NULL;
626 #endif
627
628     g_return_val_if_fail(cache != NULL, NULL);
629     g_return_val_if_fail(name != NULL, NULL);
630
631     set = g_hash_table_lookup(cache->name_table, name);
632     if (set) {
633         self = set->images->data;
634         RrImageRef(self);
635         return self;
636     }
637
638     /* XXX find the path via freedesktop icon spec (use obt) ! */
639     path = g_strdup(name);
640
641     loaded = FALSE;
642 #if defined(USE_LIBRSVG)
643     if (!loaded) {
644         rsvg_loader = LoadWithRsvg(path, &data, &w, &h);
645         loaded = !!rsvg_loader;
646     }
647 #endif
648 #if defined(USE_IMLIB2)
649     if (!loaded) {
650         imlib_loader = LoadWithImlib(path, &data, &w, &h);
651         loaded = !!imlib_loader;
652     }
653 #endif
654
655     if (!loaded) {
656         g_message("Cannot load image \"%s\" from file \"%s\"", name, path);
657         g_free(path);
658 #if defined(USE_LIBRSVG)
659         DestroyRsvgLoader(rsvg_loader);
660 #endif
661 #if defined(USE_IMLIB2)
662         DestroyImlibLoader(imlib_loader);
663 #endif
664         return NULL;
665     }
666
667     g_free(path);
668
669     /* get an RrImage that contains an RrImageSet with this picture in it.
670        the RrImage might be new, or reused if the picture was already in the
671        cache.
672
673        either way, we get back an RrImageSet (via the RrImage), and we must add
674        the name to that RrImageSet.  because of the check above, we know that
675        there is no RrImageSet in the cache which already has the given name
676        asosciated with it.
677     */
678
679     self = RrImageNewFromData(cache, data, w, h);
680     RrImageSetAddName(self->set, name);
681
682 #if defined(USE_LIBRSVG)
683     DestroyRsvgLoader(rsvg_loader);
684 #endif
685 #if defined(USE_IMLIB2)
686     DestroyImlibLoader(imlib_loader);
687 #endif
688
689     return self;
690 }
691
692 /************************************************************************
693  Image drawing and resizing operations.
694 **************************************************************************/
695
696 /*! Given a picture in RGBA format, of a specified size, resize it to the new
697   requested size (but keep its aspect ratio).  If the image does not need to
698   be resized (it is already the right size) then this returns NULL.  Otherwise
699   it returns a newly allocated RrImagePic with the resized picture inside it
700   @return Returns a newly allocated RrImagePic object with a new version of the
701     image in the requested size (keeping aspect ratio).
702 */
703 static RrImagePic* ResizeImage(RrPixel32 *src,
704                                gulong srcW, gulong srcH,
705                                gulong dstW, gulong dstH)
706 {
707     RrPixel32 *dst, *dststart;
708     RrImagePic *pic;
709     gulong dstX, dstY, srcX, srcY;
710     gulong srcX1, srcX2, srcY1, srcY2;
711     gulong ratioX, ratioY;
712     gulong aspectW, aspectH;
713
714     g_assert(srcW > 0);
715     g_assert(srcH > 0);
716     g_assert(dstW > 0);
717     g_assert(dstH > 0);
718
719     /* keep the aspect ratio */
720     aspectW = dstW;
721     aspectH = (gint)(dstW * ((gdouble)srcH / srcW));
722     if (aspectH > dstH) {
723         aspectH = dstH;
724         aspectW = (gint)(dstH * ((gdouble)srcW / srcH));
725     }
726     dstW = aspectW ? aspectW : 1;
727     dstH = aspectH ? aspectH : 1;
728
729     if (srcW == dstW && srcH == dstH)
730         return NULL; /* no scaling needed! */
731
732     dststart = dst = g_new(RrPixel32, dstW * dstH);
733
734     ratioX = (srcW << FRACTION) / dstW;
735     ratioY = (srcH << FRACTION) / dstH;
736
737     srcY2 = 0;
738     for (dstY = 0; dstY < dstH; dstY++) {
739         srcY1 = srcY2;
740         srcY2 += ratioY;
741
742         srcX2 = 0;
743         for (dstX = 0; dstX < dstW; dstX++) {
744             gulong red = 0, green = 0, blue = 0, alpha = 0;
745             gulong portionX, portionY, portionXY, sumXY = 0;
746             RrPixel32 pixel;
747
748             srcX1 = srcX2;
749             srcX2 += ratioX;
750
751             for (srcY = srcY1; srcY < srcY2; srcY += (1UL << FRACTION)) {
752                 if (srcY == srcY1) {
753                     srcY = FLOOR(srcY);
754                     portionY = (1UL << FRACTION) - (srcY1 - srcY);
755                     if (portionY > srcY2 - srcY1)
756                         portionY = srcY2 - srcY1;
757                 }
758                 else if (srcY == FLOOR(srcY2))
759                     portionY = srcY2 - srcY;
760                 else
761                     portionY = (1UL << FRACTION);
762
763                 for (srcX = srcX1; srcX < srcX2; srcX += (1UL << FRACTION)) {
764                     if (srcX == srcX1) {
765                         srcX = FLOOR(srcX);
766                         portionX = (1UL << FRACTION) - (srcX1 - srcX);
767                         if (portionX > srcX2 - srcX1)
768                             portionX = srcX2 - srcX1;
769                     }
770                     else if (srcX == FLOOR(srcX2))
771                         portionX = srcX2 - srcX;
772                     else
773                         portionX = (1UL << FRACTION);
774
775                     portionXY = (portionX * portionY) >> FRACTION;
776                     sumXY += portionXY;
777
778                     pixel = *(src + (srcY >> FRACTION) * srcW
779                             + (srcX >> FRACTION));
780                     red   += ((pixel >> RrDefaultRedOffset)   & 0xFF)
781                              * portionXY;
782                     green += ((pixel >> RrDefaultGreenOffset) & 0xFF)
783                              * portionXY;
784                     blue  += ((pixel >> RrDefaultBlueOffset)  & 0xFF)
785                              * portionXY;
786                     alpha += ((pixel >> RrDefaultAlphaOffset) & 0xFF)
787                              * portionXY;
788                 }
789             }
790
791             g_assert(sumXY != 0);
792             red   /= sumXY;
793             green /= sumXY;
794             blue  /= sumXY;
795             alpha /= sumXY;
796
797             *dst++ = (red   << RrDefaultRedOffset)   |
798                      (green << RrDefaultGreenOffset) |
799                      (blue  << RrDefaultBlueOffset)  |
800                      (alpha << RrDefaultAlphaOffset);
801         }
802     }
803
804     pic = g_slice_new(RrImagePic);
805     RrImagePicInit(pic, dstW, dstH, dststart);
806
807     return pic;
808 }
809
810 /*! This draws an RGBA picture into the target, within the rectangle specified
811   by the area parameter.  If the area's size differs from the source's then it
812   will be centered within the rectangle */
813 void DrawRGBA(RrPixel32 *target, gint target_w, gint target_h,
814               RrPixel32 *source, gint source_w, gint source_h,
815               gint alpha, RrRect *area)
816 {
817     RrPixel32 *dest;
818     gint col, num_pixels;
819     gint dw, dh;
820
821     g_assert(source_w <= area->width && source_h <= area->height);
822     g_assert(area->x + area->width <= target_w);
823     g_assert(area->y + area->height <= target_h);
824
825     /* keep the aspect ratio */
826     dw = area->width;
827     dh = (gint)(dw * ((gdouble)source_h / source_w));
828     if (dh > area->height) {
829         dh = area->height;
830         dw = (gint)(dh * ((gdouble)source_w / source_h));
831     }
832
833     /* copy source -> dest, and apply the alpha channel.
834        center the image if it is smaller than the area */
835     col = 0;
836     num_pixels = dw * dh;
837     dest = target + area->x + (area->width - dw) / 2 +
838         (target_w * (area->y + (area->height - dh) / 2));
839     while (num_pixels-- > 0) {
840         guchar a, r, g, b, bgr, bgg, bgb;
841
842         /* apply the rgba's opacity as well */
843         a = ((*source >> RrDefaultAlphaOffset) * alpha) >> 8;
844         r = *source >> RrDefaultRedOffset;
845         g = *source >> RrDefaultGreenOffset;
846         b = *source >> RrDefaultBlueOffset;
847
848         /* background color */
849         bgr = *dest >> RrDefaultRedOffset;
850         bgg = *dest >> RrDefaultGreenOffset;
851         bgb = *dest >> RrDefaultBlueOffset;
852
853         r = bgr + (((r - bgr) * a) >> 8);
854         g = bgg + (((g - bgg) * a) >> 8);
855         b = bgb + (((b - bgb) * a) >> 8);
856
857         *dest = ((r << RrDefaultRedOffset) |
858                  (g << RrDefaultGreenOffset) |
859                  (b << RrDefaultBlueOffset));
860
861         dest++;
862         source++;
863
864         if (++col >= dw) {
865             col = 0;
866             dest += target_w - dw;
867         }
868     }
869 }
870
871 /*! Draw an RGBA texture into a target pixel buffer. */
872 void RrImageDrawRGBA(RrPixel32 *target, RrTextureRGBA *rgba,
873                      gint target_w, gint target_h,
874                      RrRect *area)
875 {
876     RrImagePic *scaled;
877
878     scaled = ResizeImage(rgba->data, rgba->width, rgba->height,
879                          area->width, area->height);
880
881     if (scaled) {
882 #ifdef DEBUG
883             g_warning("Scaling an RGBA! You should avoid this and just make "
884                       "it the right size yourself!");
885 #endif
886             DrawRGBA(target, target_w, target_h,
887                      scaled->data, scaled->width, scaled->height,
888                      rgba->alpha, area);
889             RrImagePicFree(scaled);
890     }
891     else
892         DrawRGBA(target, target_w, target_h,
893                  rgba->data, rgba->width, rgba->height,
894                  rgba->alpha, area);
895 }
896
897 /*! Draw an RrImage texture into a target pixel buffer.  If the RrImage does
898   not contain a picture of the appropriate size, then one of its "original"
899   pictures will be resized and used (and stored in the RrImage as a "resized"
900   picture).
901  */
902 void RrImageDrawImage(RrPixel32 *target, RrTextureImage *img,
903                       gint target_w, gint target_h,
904                       RrRect *area)
905 {
906     gint i, min_diff, min_i, min_aspect_diff, min_aspect_i;
907     RrImage *self;
908     RrImageSet *set;
909     RrImagePic *pic;
910     gboolean free_pic;
911
912     self = img->image;
913     set = self->set;
914     pic = NULL;
915     free_pic = FALSE;
916
917     /* is there an original of this size? (only the larger of
918        w or h has to be right cuz we maintain aspect ratios) */
919     for (i = 0; i < set->n_original; ++i)
920         if ((set->original[i]->width >= set->original[i]->height &&
921              set->original[i]->width == area->width) ||
922             (set->original[i]->width <= set->original[i]->height &&
923              set->original[i]->height == area->height))
924         {
925             pic = set->original[i];
926             break;
927         }
928
929     /* is there a resize of this size? */
930     for (i = 0; i < set->n_resized; ++i)
931         if ((set->resized[i]->width >= set->resized[i]->height &&
932              set->resized[i]->width == area->width) ||
933             (set->resized[i]->width <= set->resized[i]->height &&
934              set->resized[i]->height == area->height))
935         {
936             gint j;
937             RrImagePic *saved;
938
939             /* save the selected one */
940             saved = set->resized[i];
941
942             /* shift all the others down */
943             for (j = i; j > 0; --j)
944                 set->resized[j] = set->resized[j-1];
945
946             /* and move the selected one to the top of the list */
947             set->resized[0] = saved;
948
949             pic = set->resized[0];
950             break;
951         }
952
953     if (!pic) {
954         gdouble aspect;
955         RrImageSet *cache_set;
956
957         /* find an original with a close size */
958         min_diff = min_aspect_diff = -1;
959         min_i = min_aspect_i = 0;
960         aspect = ((gdouble)area->width) / area->height;
961         for (i = 0; i < set->n_original; ++i) {
962             gint diff;
963             gint wdiff, hdiff;
964             gdouble myasp;
965
966             /* our size difference metric.. */
967             wdiff = set->original[i]->width - area->width;
968             if (wdiff < 0) wdiff *= 2; /* prefer scaling down than up */
969             hdiff = set->original[i]->height - area->height;
970             if (hdiff < 0) hdiff *= 2; /* prefer scaling down than up */
971             diff = (wdiff * wdiff) + (hdiff * hdiff);
972
973             /* find the smallest difference */
974             if (min_diff < 0 || diff < min_diff) {
975                 min_diff = diff;
976                 min_i = i;
977             }
978             /* and also find the smallest difference with the same aspect
979                ratio (and prefer this one) */
980             myasp = ((gdouble)set->original[i]->width) /
981                 set->original[i]->height;
982             if (ABS(aspect - myasp) < 0.0000001 &&
983                 (min_aspect_diff < 0 || diff < min_aspect_diff))
984             {
985                 min_aspect_diff = diff;
986                 min_aspect_i = i;
987             }
988         }
989
990         /* use the aspect ratio correct source if there is one */
991         if (min_aspect_i >= 0)
992             min_i = min_aspect_i;
993
994         /* resize the original to the given area */
995         pic = ResizeImage(set->original[min_i]->data,
996                           set->original[min_i]->width,
997                           set->original[min_i]->height,
998                           area->width, area->height);
999
1000         /* is it already in the cache ? */
1001         cache_set = g_hash_table_lookup(set->cache->pic_table, pic);
1002         if (cache_set) {
1003             /* merge this set with the one found in the cache - they are
1004                apparently the same image !  then next time we won't have to do
1005                this resizing, we will use the cache_set's pic instead. */
1006             set = RrImageSetMergeSets(set, cache_set);
1007             free_pic = TRUE;
1008         }
1009         else {
1010             /* add the resized image to the image, as the first in the resized
1011                list */
1012             while (set->n_resized >= set->cache->max_resized_saved)
1013                 /* remove the last one (last used one) to make space for
1014                  adding our resized picture */
1015                 RrImageSetRemovePictureAt(set, set->n_resized-1, FALSE);
1016             if (set->cache->max_resized_saved)
1017                 /* add it to the resized list */
1018                 RrImageSetAddPicture(set, pic, FALSE);
1019             else
1020                 free_pic = TRUE; /* don't leak mem! */
1021         }
1022     }
1023
1024     /* The RrImageSet may have changed if we merged it with another, so the
1025        RrImage object needs to be updated to use the new merged RrImageSet. */
1026     self->set = set;
1027
1028     g_assert(pic != NULL);
1029
1030     DrawRGBA(target, target_w, target_h,
1031              pic->data, pic->width, pic->height,
1032              img->alpha, area);
1033     if (free_pic)
1034         RrImagePicFree(pic);
1035 }