source: libcaca/trunk/cucul/dither.c @ 769

Last change on this file since 769 was 769, checked in by Sam Hocevar, 14 years ago
  • Removed \file directives from all files except caca.h and cucul.h, to remove redundencies in the Doxygen documentation.
  • Property svn:keywords set to Id
File size: 35.3 KB
Line 
1/*
2 *  libcucul      Canvas for ultrafast compositing of Unicode letters
3 *  Copyright (c) 2002-2006 Sam Hocevar <sam@zoy.org>
4 *                All Rights Reserved
5 *
6 *  $Id: dither.c 769 2006-04-14 07:30:53Z sam $
7 *
8 *  This library is free software; you can redistribute it and/or
9 *  modify it under the terms of the Do What The Fuck You Want To
10 *  Public License, Version 2, as published by Sam Hocevar. See
11 *  http://sam.zoy.org/wtfpl/COPYING for more details.
12 */
13
14/*
15 *  This file contains bitmap dithering functions.
16 */
17
18#include "config.h"
19
20#if !defined(__KERNEL__)
21#   if defined(HAVE_ENDIAN_H)
22#       include <endian.h>
23#   endif
24#   include <stdio.h>
25#   include <stdlib.h>
26#   include <limits.h>
27#   include <string.h>
28#endif
29
30#include "cucul.h"
31#include "cucul_internals.h"
32
33#define CP437 0
34
35/*
36 * Local variables
37 */
38#if !defined(_DOXYGEN_SKIP_ME)
39#   define LOOKUP_VAL 32
40#   define LOOKUP_SAT 32
41#   define LOOKUP_HUE 16
42#endif
43static unsigned char hsv_distances[LOOKUP_VAL][LOOKUP_SAT][LOOKUP_HUE];
44static uint16_t lookup_colors[8];
45
46static int const hsv_palette[] =
47{
48    /* weight, hue, saturation, value */
49    4,    0x0,    0x0,    0x0,   /* black */
50    5,    0x0,    0x0,    0x5ff, /* 30% */
51    5,    0x0,    0x0,    0x9ff, /* 70% */
52    4,    0x0,    0x0,    0xfff, /* white */
53    3,    0x1000, 0xfff,  0x5ff, /* dark yellow */
54    2,    0x1000, 0xfff,  0xfff, /* light yellow */
55    3,    0x0,    0xfff,  0x5ff, /* dark red */
56    2,    0x0,    0xfff,  0xfff  /* light red */
57};
58
59/* RGB palette for the new colour picker */
60static int const rgb_palette[] =
61{
62    0x0,   0x0,   0x0,
63    0x0,   0x0,   0x7ff,
64    0x0,   0x7ff, 0x0,
65    0x0,   0x7ff, 0x7ff,
66    0x7ff, 0x0,   0x0,
67    0x7ff, 0x0,   0x7ff,
68    0x7ff, 0x7ff, 0x0,
69    0xaaa, 0xaaa, 0xaaa,
70    0x555, 0x555, 0x555,
71    0x000, 0x000, 0xfff,
72    0x000, 0xfff, 0x000,
73    0x000, 0xfff, 0xfff,
74    0xfff, 0x000, 0x000,
75    0xfff, 0x000, 0xfff,
76    0xfff, 0xfff, 0x000,
77    0xfff, 0xfff, 0xfff,
78};
79
80static int const rgb_weight[] =
81{
82    //2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2
83    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
84};
85
86/* List of glyphs */
87static char const * ascii_glyphs[] =
88{
89    " ", ".", ":", ";", "t", "%", "S", "X", "@", "8", "?"
90};
91
92static char const * shades_glyphs[] =
93{
94    " ", ":", "░", "▒", "?"
95};
96
97static char const * blocks_glyphs[] =
98{
99    " ", "▘", "▚", "?"
100};
101
102#if !defined(_DOXYGEN_SKIP_ME)
103enum color_mode
104{
105    COLOR_MODE_MONO,
106    COLOR_MODE_GRAY,
107    COLOR_MODE_8,
108    COLOR_MODE_16,
109    COLOR_MODE_FULLGRAY,
110    COLOR_MODE_FULL8,
111    COLOR_MODE_FULL16,
112};
113
114struct cucul_dither
115{
116    int bpp, has_palette, has_alpha;
117    int w, h, pitch;
118    int rmask, gmask, bmask, amask;
119    int rright, gright, bright, aright;
120    int rleft, gleft, bleft, aleft;
121    void (*get_hsv)(struct cucul_dither *, char *, int, int);
122    int red[256], green[256], blue[256], alpha[256];
123    float gamma;
124    int gammatab[4097];
125
126    /* Bitmap features */
127    int invert, antialias;
128
129    /* Colour mode used for rendering */
130    enum color_mode color_mode;
131
132    /* Glyphs used for rendering */
133    char const * const * glyphs;
134    unsigned glyph_count;
135
136    /* Current dithering method */
137    void (*init_dither) (int);
138    unsigned int (*get_dither) (void);
139    void (*increment_dither) (void);
140};
141
142#define HSV_XRATIO 6
143#define HSV_YRATIO 3
144#define HSV_HRATIO 3
145
146#define HSV_DISTANCE(h, s, v, index) \
147    (hsv_palette[index * 4] \
148     * ((HSV_XRATIO * ((v) - hsv_palette[index * 4 + 3]) \
149                    * ((v) - hsv_palette[index * 4 + 3])) \
150       + (hsv_palette[index * 4 + 3] \
151           ? (HSV_YRATIO * ((s) - hsv_palette[index * 4 + 2]) \
152                         * ((s) - hsv_palette[index * 4 + 2])) \
153           : 0) \
154       + (hsv_palette[index * 4 + 2] \
155           ? (HSV_HRATIO * ((h) - hsv_palette[index * 4 + 1]) \
156                         * ((h) - hsv_palette[index * 4 + 1])) \
157           : 0)))
158#endif
159
160/*
161 * Local prototypes
162 */
163static void mask2shift(unsigned int, int *, int *);
164static float gammapow(float x, float y);
165
166static void get_rgba_default(struct cucul_dither const *, uint8_t *, int, int,
167                             unsigned int *);
168
169/* Dithering methods */
170static void init_no_dither(int);
171static unsigned int get_no_dither(void);
172static void increment_no_dither(void);
173
174static void init_fstein_dither(int);
175static unsigned int get_fstein_dither(void);
176static void increment_fstein_dither(void);
177
178static void init_ordered2_dither(int);
179static unsigned int get_ordered2_dither(void);
180static void increment_ordered2_dither(void);
181
182static void init_ordered4_dither(int);
183static unsigned int get_ordered4_dither(void);
184static void increment_ordered4_dither(void);
185
186static void init_ordered8_dither(int);
187static unsigned int get_ordered8_dither(void);
188static void increment_ordered8_dither(void);
189
190static void init_random_dither(int);
191static unsigned int get_random_dither(void);
192static void increment_random_dither(void);
193
194static inline int sq(int x)
195{
196    return x * x;
197}
198
199static inline void rgb2hsv_default(int r, int g, int b,
200                                   int *hue, int *sat, int *val)
201{
202    int min, max, delta;
203
204    min = r; max = r;
205    if(min > g) min = g; if(max < g) max = g;
206    if(min > b) min = b; if(max < b) max = b;
207
208    delta = max - min; /* 0 - 0xfff */
209    *val = max; /* 0 - 0xfff */
210
211    if(delta)
212    {
213        *sat = 0xfff * delta / max; /* 0 - 0xfff */
214
215        /* Generate *hue between 0 and 0x5fff */
216        if( r == max )
217            *hue = 0x1000 + 0x1000 * (g - b) / delta;
218        else if( g == max )
219            *hue = 0x3000 + 0x1000 * (b - r) / delta;
220        else
221            *hue = 0x5000 + 0x1000 * (r - g) / delta;
222    }
223    else
224    {
225        *sat = 0;
226        *hue = 0;
227    }
228}
229
230/**
231 * \brief Create an internal dither object.
232 *
233 * Create a dither structure from its coordinates (depth, width, height and
234 * pitch) and pixel mask values. If the depth is 8 bits per pixel, the mask
235 * values are ignored and the colour palette should be set using the
236 * cucul_set_dither_palette() function. For depths greater than 8 bits per
237 * pixel, a zero alpha mask causes the alpha values to be ignored.
238 *
239 * \param bpp Bitmap depth in bits per pixel.
240 * \param w Bitmap width in pixels.
241 * \param h Bitmap height in pixels.
242 * \param pitch Bitmap pitch in bytes.
243 * \param rmask Bitmask for red values.
244 * \param gmask Bitmask for green values.
245 * \param bmask Bitmask for blue values.
246 * \param amask Bitmask for alpha values.
247 * \return Dither object, or NULL upon error.
248 */
249struct cucul_dither *cucul_create_dither(unsigned int bpp, unsigned int w,
250                                         unsigned int h, unsigned int pitch,
251                                         unsigned int rmask, unsigned int gmask,
252                                         unsigned int bmask, unsigned int amask)
253{
254    struct cucul_dither *d;
255    int i;
256
257    /* Minor sanity test */
258    if(!w || !h || !pitch || bpp > 32 || bpp < 8)
259        return NULL;
260
261    d = malloc(sizeof(struct cucul_dither));
262    if(!d)
263        return NULL;
264
265    d->bpp = bpp;
266    d->has_palette = 0;
267    d->has_alpha = amask ? 1 : 0;
268
269    d->w = w;
270    d->h = h;
271    d->pitch = pitch;
272
273    d->rmask = rmask;
274    d->gmask = gmask;
275    d->bmask = bmask;
276    d->amask = amask;
277
278    /* Load bitmasks */
279    if(rmask || gmask || bmask || amask)
280    {
281        mask2shift(rmask, &d->rright, &d->rleft);
282        mask2shift(gmask, &d->gright, &d->gleft);
283        mask2shift(bmask, &d->bright, &d->bleft);
284        mask2shift(amask, &d->aright, &d->aleft);
285    }
286
287    /* In 8 bpp mode, default to a grayscale palette */
288    if(bpp == 8)
289    {
290        d->has_palette = 1;
291        d->has_alpha = 0;
292        for(i = 0; i < 256; i++)
293        {
294            d->red[i] = i * 0xfff / 256;
295            d->green[i] = i * 0xfff / 256;
296            d->blue[i] = i * 0xfff / 256;
297        }
298    }
299
300    /* Default features */
301    d->invert = 0;
302    d->antialias = 1;
303
304    /* Default gamma value */
305    for(i = 0; i < 4096; i++)
306        d->gammatab[i] = i;
307
308    /* Default colour mode */
309    d->color_mode = COLOR_MODE_FULL16;
310
311    /* Default character set */
312    d->glyphs = ascii_glyphs;
313    d->glyph_count = sizeof(ascii_glyphs) / sizeof(*ascii_glyphs);
314
315    /* Default dithering mode */
316    d->init_dither = init_fstein_dither;
317    d->get_dither = get_fstein_dither;
318    d->increment_dither = increment_fstein_dither;
319
320    return d;
321}
322
323/**
324 * \brief Set the palette of an 8bpp dither object.
325 *
326 * Set the palette of an 8 bits per pixel bitmap. Values should be between
327 * 0 and 4095 (0xfff).
328 *
329 * \param dither Dither object.
330 * \param red Array of 256 red values.
331 * \param green Array of 256 green values.
332 * \param blue Array of 256 blue values.
333 * \param alpha Array of 256 alpha values.
334 */
335void cucul_set_dither_palette(struct cucul_dither *d,
336                              unsigned int red[], unsigned int green[],
337                              unsigned int blue[], unsigned int alpha[])
338{
339    int i, has_alpha = 0;
340
341    if(d->bpp != 8)
342        return;
343
344    for(i = 0; i < 256; i++)
345    {
346        if(red[i] >= 0 && red[i] < 0x1000 &&
347           green[i] >= 0 && green[i] < 0x1000 &&
348           blue[i] >= 0 && blue[i] < 0x1000 &&
349           alpha[i] >= 0 && alpha[i] < 0x1000)
350        {
351            d->red[i] = red[i];
352            d->green[i] = green[i];
353            d->blue[i] = blue[i];
354            if(alpha[i])
355            {
356                d->alpha[i] = alpha[i];
357                has_alpha = 1;
358            }
359        }
360    }
361
362    d->has_alpha = has_alpha;
363}
364
365/**
366 * \brief Set the brightness of a dither object.
367 *
368 * Set the brightness of dither.
369 *
370 * \param dither Dither object.
371 * \param brightness brightness value.
372 */
373void cucul_set_dither_brightness(struct cucul_dither *d, float brightness)
374{
375    /* FIXME */
376}
377
378/**
379 * \brief Set the gamma of a dither object.
380 *
381 * Set the gamma of dither.
382 *
383 * \param dither Dither object.
384 * \param gamma Gamma value.
385 */
386void cucul_set_dither_gamma(struct cucul_dither *d, float gamma)
387{
388    /* FIXME: we don't need 4096 calls to gammapow(), we can just compute
389     * 128 of them and do linear interpolation for the rest. This will
390     * probably speed up things a lot. */
391    int i;
392
393    if(gamma <= 0.0)
394        return;
395
396    d->gamma = gamma;
397
398    for(i = 0; i < 4096; i++)
399        d->gammatab[i] = 4096.0 * gammapow((float)i / 4096.0, 1.0 / gamma);
400}
401
402/**
403 * \brief Invert colors of dither
404 *
405 * Invert colors of dither
406 *
407 * \param dither Dither object.
408 * \param value 0 for normal behaviour, 1 for invert
409 */
410void cucul_set_dither_invert(struct cucul_dither *d, int value)
411{
412    d->invert = value ? 1 : 0;
413}
414
415/**
416 * \brief Set the contrast of a dither object.
417 *
418 * Set the contrast of dither.
419 *
420 * \param dither Dither object.
421 * \param contrast contrast value.
422 */
423void cucul_set_dither_contrast(struct cucul_dither *d, float contrast)
424{
425    /* FIXME */
426}
427
428/**
429 * \brief Set dither antialiasing
430 *
431 * Tell the renderer whether to antialias the dither. Antialiasing smoothen
432 * the rendered image and avoids the commonly seen staircase effect.
433 *
434 * \li \e "none": no antialiasing.
435 *
436 * \li \e "prefilter": simple prefilter antialiasing. This is the default
437 *     value.
438 *
439 * \param dither Dither object.
440 * \param str A string describing the antialiasing method that will be used
441 *        for the dithering.
442 */
443void cucul_set_dither_antialias(struct cucul_dither *d, char const *str)
444{
445    if(!strcasecmp(str, "none"))
446        d->antialias = 0;
447    else /* "prefilter" is the default */
448        d->antialias = 1;
449}
450
451/**
452 * \brief Get available antialiasing methods
453 *
454 * Return a list of available antialiasing methods for a given dither. The
455 * list is a NULL-terminated array of strings, interleaving a string
456 * containing the internal value for the antialiasing method to be used with
457 * \e cucul_set_dither_antialias(), and a string containing the natural
458 * language description for that antialiasing method.
459 *
460 * \param dither Dither object.
461 * \return An array of strings.
462 */
463char const * const *
464    cucul_get_dither_antialias_list(struct cucul_dither const *d)
465{
466    static char const * const list[] =
467    {
468        "none", "No antialiasing",
469        "prefilter", "Prefilter antialiasing",
470        NULL, NULL
471    };
472
473    return list;
474}
475
476/**
477 * \brief Choose colours used for dithering
478 *
479 * Tell the renderer which colours should be used to render the
480 * bitmap. Valid values for \e str are:
481 *
482 * \li \e "mono": use light gray on a black background.
483 *
484 * \li \e "gray": use white and two shades of gray on a black background.
485 *
486 * \li \e "8": use the 8 ANSI colours on a black background.
487 *
488 * \li \e "16": use the 16 ANSI colours on a black background.
489 *
490 * \li \e "fullgray": use black, white and two shades of gray for both the
491 *     characters and the background.
492 *
493 * \li \e "full8": use the 8 ANSI colours for both the characters and the
494 *     background.
495 *
496 * \li \e "full16": use the 16 ANSI colours for both the characters and the
497 *     background. This is the default value.
498 *
499 * \param dither Dither object.
500 * \param str A string describing the colour set that will be used
501 *        for the dithering.
502 */
503void cucul_set_dither_color(struct cucul_dither *d, char const *str)
504{
505    if(!strcasecmp(str, "mono"))
506        d->color_mode = COLOR_MODE_MONO;
507    else if(!strcasecmp(str, "gray"))
508        d->color_mode = COLOR_MODE_GRAY;
509    else if(!strcasecmp(str, "8"))
510        d->color_mode = COLOR_MODE_8;
511    else if(!strcasecmp(str, "16"))
512        d->color_mode = COLOR_MODE_16;
513    else if(!strcasecmp(str, "fullgray"))
514        d->color_mode = COLOR_MODE_FULLGRAY;
515    else if(!strcasecmp(str, "full8"))
516        d->color_mode = COLOR_MODE_FULL8;
517    else /* "full16" is the default */
518        d->color_mode = COLOR_MODE_FULL16;
519}
520
521/**
522 * \brief Get available colour modes
523 *
524 * Return a list of available colour modes for a given dither. The list
525 * is a NULL-terminated array of strings, interleaving a string containing
526 * the internal value for the colour mode, to be used with
527 * \e cucul_set_dither_color(), and a string containing the natural
528 * language description for that colour mode.
529 *
530 * \param dither Dither object.
531 * \return An array of strings.
532 */
533char const * const *
534    cucul_get_dither_color_list(struct cucul_dither const *d)
535{
536    static char const * const list[] =
537    {
538        "mono", "white on black",
539        "gray", "grayscale on black",
540        "8", "8 colours on black",
541        "16", "16 colours on black",
542        "fullgray", "full grayscale",
543        "full8", "full 8 colours",
544        "full16", "full 16 colours",
545        NULL, NULL
546    };
547
548    return list;
549}
550
551/**
552 * \brief Choose characters used for dithering
553 *
554 * Tell the renderer which characters should be used to render the
555 * dither. Valid values for \e str are:
556 *
557 * \li \e "ascii": use only ASCII characters. This is the default value.
558 *
559 * \li \e "shades": use Unicode characters "U+2591 LIGHT SHADE", "U+2592
560 *     MEDIUM SHADE" and "U+2593 DARK SHADE". These characters are also
561 *     present in the CP437 codepage available on DOS and VGA.
562 *
563 * \li \e "blocks": use Unicode quarter-cell block combinations. These
564 *     characters are only found in the Unicode set.
565 *
566 * \param dither Dither object.
567 * \param str A string describing the characters that need to be used
568 *        for the dithering.
569 */
570void cucul_set_dither_charset(struct cucul_dither *d, char const *str)
571{
572    if(!strcasecmp(str, "shades"))
573    {
574        d->glyphs = shades_glyphs;
575        d->glyph_count = sizeof(shades_glyphs) / sizeof(*shades_glyphs);
576    }
577    else if(!strcasecmp(str, "blocks"))
578    {
579        d->glyphs = blocks_glyphs;
580        d->glyph_count = sizeof(blocks_glyphs) / sizeof(*blocks_glyphs);
581    }
582    else /* "ascii" is the default */
583    {
584        d->glyphs = ascii_glyphs;
585        d->glyph_count = sizeof(ascii_glyphs) / sizeof(*ascii_glyphs);
586    }
587}
588
589/**
590 * \brief Get available dither character sets
591 *
592 * Return a list of available character sets for a given dither. The list
593 * is a NULL-terminated array of strings, interleaving a string containing
594 * the internal value for the character set, to be used with
595 * \e cucul_set_dither_charset(), and a string containing the natural
596 * language description for that character set.
597 *
598 * \param dither Dither object.
599 * \return An array of strings.
600 */
601char const * const *
602    cucul_get_dither_charset_list(struct cucul_dither const *d)
603{
604    static char const * const list[] =
605    {
606        "ascii", "plain ASCII",
607        "shades", "CP437 shades",
608        "blocks", "Unicode blocks",
609        NULL, NULL
610    };
611
612    return list;
613}
614
615/**
616 * \brief Set dithering method
617 *
618 * Tell the renderer which dithering method should be used. Dithering is
619 * necessary because the picture being rendered has usually far more colours
620 * than the available palette. Valid values for \e str are:
621 *
622 * \li \e "none": no dithering is used, the nearest matching colour is used.
623 *
624 * \li \e "ordered2": use a 2x2 Bayer matrix for dithering.
625 *
626 * \li \e "ordered4": use a 4x4 Bayer matrix for dithering.
627 *
628 * \li \e "ordered8": use a 8x8 Bayer matrix for dithering.
629 *
630 * \li \e "random": use random dithering.
631 *
632 * \li \e "fstein": use Floyd-Steinberg dithering. This is the default value.
633 *
634 * \param dither Dither object.
635 * \param str A string describing the method that needs to be used
636 *        for the dithering.
637 */
638void cucul_set_dither_mode(struct cucul_dither *d, char const *str)
639{
640    if(!strcasecmp(str, "none"))
641    {
642        d->init_dither = init_no_dither;
643        d->get_dither = get_no_dither;
644        d->increment_dither = increment_no_dither;
645    }
646    else if(!strcasecmp(str, "ordered2"))
647    {
648        d->init_dither = init_ordered2_dither;
649        d->get_dither = get_ordered2_dither;
650        d->increment_dither = increment_ordered2_dither;
651    }
652    else if(!strcasecmp(str, "ordered4"))
653    {
654        d->init_dither = init_ordered4_dither;
655        d->get_dither = get_ordered4_dither;
656        d->increment_dither = increment_ordered4_dither;
657    }
658    else if(!strcasecmp(str, "ordered4"))
659    {
660        d->init_dither = init_ordered8_dither;
661        d->get_dither = get_ordered8_dither;
662        d->increment_dither = increment_ordered8_dither;
663    }
664    else if(!strcasecmp(str, "random"))
665    {
666        d->init_dither = init_random_dither;
667        d->get_dither = get_random_dither;
668        d->increment_dither = increment_random_dither;
669    }
670    else /* "fstein" is the default */
671    {
672        d->init_dither = init_fstein_dither;
673        d->get_dither = get_fstein_dither;
674        d->increment_dither = increment_fstein_dither;
675    }
676}
677
678/**
679 * \brief Get dithering methods
680 *
681 * Return a list of available dithering methods for a given dither. The list
682 * is a NULL-terminated array of strings, interleaving a string containing
683 * the internal value for the dithering method, to be used with
684 * \e cucul_set_dither_dithering(), and a string containing the natural
685 * language description for that dithering method.
686 *
687 * \param dither Dither object.
688 * \return An array of strings.
689 */
690char const * const *
691    cucul_get_dither_mode_list(struct cucul_dither const *d)
692{
693    static char const * const list[] =
694    {
695        "none", "no dithering",
696        "ordered2", "2x2 ordered dithering",
697        "ordered2", "2x2 ordered dithering",
698        "ordered2", "2x2 ordered dithering",
699        "random", "random dithering",
700        "fstein", "Floyd-Steinberg dithering",
701        NULL, NULL
702    };
703
704    return list;
705}
706
707/**
708 * \brief Draw a dither on the screen.
709 *
710 * Draw a dither at the given coordinates. The dither can be of any size and
711 * will be stretched to the text area.
712 *
713 * \param x1 X coordinate of the upper-left corner of the drawing area.
714 * \param y1 Y coordinate of the upper-left corner of the drawing area.
715 * \param x2 X coordinate of the lower-right corner of the drawing area.
716 * \param y2 Y coordinate of the lower-right corner of the drawing area.
717 * \param dither Dither object to be drawn.
718 * \param pixels Bitmap's pixels.
719 */
720void cucul_dither_bitmap(cucul_t *qq, int x1, int y1, int x2, int y2,
721                         struct cucul_dither const *d, void *pixels)
722{
723    int *floyd_steinberg, *fs_r, *fs_g, *fs_b;
724    int fs_length;
725    int x, y, w, h, pitch, deltax, deltay;
726    unsigned int dchmax;
727
728    if(!d || !pixels)
729        return;
730
731    w = d->w;
732    h = d->h;
733    pitch = d->pitch;
734
735    if(x1 > x2)
736    {
737        int tmp = x2; x2 = x1; x1 = tmp;
738    }
739
740    if(y1 > y2)
741    {
742        int tmp = y2; y2 = y1; y1 = tmp;
743    }
744
745    deltax = x2 - x1 + 1;
746    deltay = y2 - y1 + 1;
747    dchmax = d->glyph_count;
748
749    fs_length = ((int)qq->width <= x2 ? (int)qq->width : x2) + 1;
750    floyd_steinberg = malloc(3 * (fs_length + 2) * sizeof(int));
751    memset(floyd_steinberg, 0, 3 * (fs_length + 2) * sizeof(int));
752    fs_r = floyd_steinberg + 1;
753    fs_g = fs_r + fs_length + 2;
754    fs_b = fs_g + fs_length + 2;
755
756    for(y = y1 > 0 ? y1 : 0; y <= y2 && y <= (int)qq->height; y++)
757    {
758        int remain_r = 0, remain_g = 0, remain_b = 0;
759
760        for(x = x1 > 0 ? x1 : 0, d->init_dither(y);
761            x <= x2 && x <= (int)qq->width;
762            x++)
763    {
764        unsigned int i;
765        int ch = 0, distmin;
766        unsigned int rgba[4];
767        int fg_r = 0, fg_g = 0, fg_b = 0, bg_r, bg_g, bg_b;
768        int fromx, fromy, tox, toy, myx, myy, dots, dist;
769        int error[3];
770
771        unsigned int outfg = 0, outbg = 0;
772        char const *outch;
773
774        rgba[0] = rgba[1] = rgba[2] = rgba[3] = 0;
775
776        /* First get RGB */
777        if(d->antialias)
778        {
779            fromx = (x - x1) * w / deltax;
780            fromy = (y - y1) * h / deltay;
781            tox = (x - x1 + 1) * w / deltax;
782            toy = (y - y1 + 1) * h / deltay;
783
784            /* We want at least one pixel */
785            if(tox == fromx) tox++;
786            if(toy == fromy) toy++;
787
788            dots = 0;
789
790            for(myx = fromx; myx < tox; myx++)
791                for(myy = fromy; myy < toy; myy++)
792            {
793                dots++;
794                get_rgba_default(d, pixels, myx, myy, rgba);
795            }
796
797            /* Normalize */
798            rgba[0] /= dots;
799            rgba[1] /= dots;
800            rgba[2] /= dots;
801            rgba[3] /= dots;
802        }
803        else
804        {
805            fromx = (x - x1) * w / deltax;
806            fromy = (y - y1) * h / deltay;
807            tox = (x - x1 + 1) * w / deltax;
808            toy = (y - y1 + 1) * h / deltay;
809
810            /* tox and toy can overflow the screen, but they cannot overflow
811             * when averaged with fromx and fromy because these are guaranteed
812             * to be within the pixel boundaries. */
813            myx = (fromx + tox) / 2;
814            myy = (fromy + toy) / 2;
815
816            get_rgba_default(d, pixels, myx, myy, rgba);
817        }
818
819        if(d->has_alpha && rgba[3] < 0x800)
820        {
821            remain_r = remain_g = remain_b = 0;
822            fs_r[x] = 0;
823            fs_g[x] = 0;
824            fs_b[x] = 0;
825            continue;
826        }
827
828        /* XXX: OMG HAX */
829        if(d->init_dither == init_fstein_dither)
830        {
831            rgba[0] += remain_r;
832            rgba[1] += remain_g;
833            rgba[2] += remain_b;
834        }
835        else
836        {
837            rgba[0] += (d->get_dither() - 0x80) * 4;
838            rgba[1] += (d->get_dither() - 0x80) * 4;
839            rgba[2] += (d->get_dither() - 0x80) * 4;
840        }
841
842        distmin = INT_MAX;
843        for(i = 0; i < 16; i++)
844        {
845            dist = sq(rgba[0] - rgb_palette[i * 3])
846                 + sq(rgba[1] - rgb_palette[i * 3 + 1])
847                 + sq(rgba[2] - rgb_palette[i * 3 + 2]);
848            dist *= rgb_weight[i];
849            if(dist < distmin)
850            {
851                outbg = i;
852                distmin = dist;
853            }
854        }
855        bg_r = rgb_palette[outbg * 3];
856        bg_g = rgb_palette[outbg * 3 + 1];
857        bg_b = rgb_palette[outbg * 3 + 2];
858
859        /* FIXME: we currently only honour "full16" */
860        if(d->color_mode == COLOR_MODE_FULL16)
861        {
862            distmin = INT_MAX;
863            for(i = 0; i < 16; i++)
864            {
865                if(i == outbg)
866                    continue;
867                dist = sq(rgba[0] - rgb_palette[i * 3])
868                     + sq(rgba[1] - rgb_palette[i * 3 + 1])
869                     + sq(rgba[2] - rgb_palette[i * 3 + 2]);
870                dist *= rgb_weight[i];
871                if(dist < distmin)
872                {
873                    outfg = i;
874                    distmin = dist;
875                }
876            }
877            fg_r = rgb_palette[outfg * 3];
878            fg_g = rgb_palette[outfg * 3 + 1];
879            fg_b = rgb_palette[outfg * 3 + 2];
880
881            distmin = INT_MAX;
882            for(i = 0; i < dchmax - 1; i++)
883            {
884                int newr = i * fg_r + ((2*dchmax-1) - i) * bg_r;
885                int newg = i * fg_g + ((2*dchmax-1) - i) * bg_g;
886                int newb = i * fg_b + ((2*dchmax-1) - i) * bg_b;
887                dist = abs(rgba[0] * (2*dchmax-1) - newr)
888                     + abs(rgba[1] * (2*dchmax-1) - newg)
889                     + abs(rgba[2] * (2*dchmax-1) - newb);
890
891                if(dist < distmin)
892                {
893                    ch = i;
894                    distmin = dist;
895                }
896            }
897            outch = d->glyphs[ch];
898
899            /* XXX: OMG HAX */
900            if(d->init_dither == init_fstein_dither)
901            {
902                error[0] = rgba[0] - (fg_r * ch + bg_r * ((2*dchmax-1) - ch)) / (2*dchmax-1);
903                error[1] = rgba[1] - (fg_g * ch + bg_g * ((2*dchmax-1) - ch)) / (2*dchmax-1);
904                error[2] = rgba[2] - (fg_b * ch + bg_b * ((2*dchmax-1) - ch)) / (2*dchmax-1);
905            }
906        }
907        else
908        {
909            unsigned int lum = rgba[0];
910            if(rgba[1] > lum) lum = rgba[1];
911            if(rgba[2] > lum) lum = rgba[2];
912            outfg = outbg;
913            outbg = CUCUL_COLOR_BLACK;
914
915            ch = lum * dchmax / 0x1000;
916            if(ch < 0)
917                ch = 0;
918            else if(ch > (int)(dchmax - 1))
919                ch = dchmax - 1;
920            outch = d->glyphs[ch];
921
922            /* XXX: OMG HAX */
923            if(d->init_dither == init_fstein_dither)
924            {
925                error[0] = rgba[0] - bg_r * ch / (dchmax-1);
926                error[1] = rgba[1] - bg_g * ch / (dchmax-1);
927                error[2] = rgba[2] - bg_b * ch / (dchmax-1);
928            }
929        }
930
931        /* XXX: OMG HAX */
932        if(d->init_dither == init_fstein_dither)
933        {
934            remain_r = fs_r[x+1] + 7 * error[0] / 16;
935            remain_g = fs_g[x+1] + 7 * error[1] / 16;
936            remain_b = fs_b[x+1] + 7 * error[2] / 16;
937            fs_r[x-1] += 3 * error[0] / 16;
938            fs_g[x-1] += 3 * error[1] / 16;
939            fs_b[x-1] += 3 * error[2] / 16;
940            fs_r[x] = 5 * error[0] / 16;
941            fs_g[x] = 5 * error[1] / 16;
942            fs_b[x] = 5 * error[2] / 16;
943            fs_r[x+1] = 1 * error[0] / 16;
944            fs_g[x+1] = 1 * error[1] / 16;
945            fs_b[x+1] = 1 * error[2] / 16;
946        }
947
948        if(d->invert)
949        {
950            outfg = 15 - outfg;
951            outbg = 15 - outbg;
952        }
953
954        /* Now output the character */
955        cucul_set_color(qq, outfg, outbg);
956        cucul_putstr(qq, x, y, outch);
957
958       d->increment_dither();
959    }
960        /* end loop */
961    }
962
963    free(floyd_steinberg);
964}
965
966/**
967 * \brief Free the memory associated with a dither.
968 *
969 * Free the memory allocated by cucul_create_dither().
970 *
971 * \param dither Dither object.
972 */
973void cucul_free_dither(struct cucul_dither *d)
974{
975    if(!d)
976        return;
977
978    free(d);
979}
980
981/*
982 * XXX: The following functions are local.
983 */
984
985/* Convert a mask, eg. 0x0000ff00, to shift values, eg. 8 and -4. */
986static void mask2shift(unsigned int mask, int *right, int *left)
987{
988    int rshift = 0, lshift = 0;
989
990    if(!mask)
991    {
992        *right = *left = 0;
993        return;
994    }
995
996    while(!(mask & 1))
997    {
998        mask >>= 1;
999        rshift++;
1000    }
1001    *right = rshift;
1002
1003    while(mask & 1)
1004    {
1005        mask >>= 1;
1006        lshift++;
1007    }
1008    *left = 12 - lshift;
1009}
1010
1011/* Compute x^y without relying on the math library */
1012static float gammapow(float x, float y)
1013{
1014#ifdef HAVE_FLDLN2
1015    register double logx;
1016    register long double v, e;
1017#else
1018    register float tmp, t, t2, r;
1019    int i;
1020#endif
1021
1022    if(x == 0.0)
1023        return y == 0.0 ? 1.0 : 0.0;
1024
1025#ifdef HAVE_FLDLN2
1026    /* FIXME: this can be optimised by directly calling fyl2x for x and y */
1027    asm volatile("fldln2; fxch; fyl2x"
1028                 : "=t" (logx) : "0" (x) : "st(1)");
1029
1030    asm volatile("fldl2e\n\t"
1031                 "fmul %%st(1)\n\t"
1032                 "fst %%st(1)\n\t"
1033                 "frndint\n\t"
1034                 "fxch\n\t"
1035                 "fsub %%st(1)\n\t"
1036                 "f2xm1\n\t"
1037                 : "=t" (v), "=u" (e) : "0" (y * logx));
1038    v += 1.0;
1039    asm volatile("fscale"
1040                 : "=t" (v) : "0" (v), "u" (e));
1041    return v;
1042#else
1043    /* Compute ln(x) for x ∈ ]0,1]
1044     *   ln(x) = 2 * (t + t^3/3 + t^5/5 + ...) with t = (x-1)/(x+1)
1045     * The convergence is a bit slow, especially when x is near 0. */
1046    t = (x - 1.0) / (x + 1.0);
1047    t2 = t * t;
1048    tmp = r = t;
1049    for(i = 3; i < 20; i += 2)
1050    {
1051        r *= t2;
1052        tmp += r / i;
1053    }
1054
1055    /* Compute -y*ln(x) */
1056    tmp = - y * 2.0 * tmp;
1057
1058    /* Compute x^-y as e^t where t = -y*ln(x):
1059     *   e^t = 1 + t/1! + t^2/2! + t^3/3! + t^4/4! + t^5/5! ...
1060     * The convergence is quite faster here, thanks to the factorial. */
1061    r = t = tmp;
1062    tmp = 1.0 + t;
1063    for(i = 2; i < 16; i++)
1064    {
1065        r = r * t / i;
1066        tmp += r;
1067    }
1068
1069    /* Return x^y as 1/(x^-y) */
1070    return 1.0 / tmp;
1071#endif
1072}
1073
1074static void get_rgba_default(struct cucul_dither const *d, uint8_t *pixels,
1075                             int x, int y, unsigned int *rgba)
1076{
1077    uint32_t bits;
1078
1079    pixels += (d->bpp / 8) * x + d->pitch * y;
1080
1081    switch(d->bpp / 8)
1082    {
1083        case 4:
1084            bits = *(uint32_t *)pixels;
1085            break;
1086        case 3:
1087        {
1088#if defined(HAVE_ENDIAN_H)
1089            if(__BYTE_ORDER == __BIG_ENDIAN)
1090#else
1091            /* This is compile-time optimised with at least -O1 or -Os */
1092            uint32_t const rmask = 0x12345678;
1093            if(*(uint8_t const *)&rmask == 0x12)
1094#endif
1095                bits = ((uint32_t)pixels[0] << 16) |
1096                       ((uint32_t)pixels[1] << 8) |
1097                       ((uint32_t)pixels[2]);
1098            else
1099                bits = ((uint32_t)pixels[2] << 16) |
1100                       ((uint32_t)pixels[1] << 8) |
1101                       ((uint32_t)pixels[0]);
1102            break;
1103        }
1104        case 2:
1105            bits = *(uint16_t *)pixels;
1106            break;
1107        case 1:
1108        default:
1109            bits = pixels[0];
1110            break;
1111    }
1112
1113    if(d->has_palette)
1114    {
1115        rgba[0] += d->gammatab[d->red[bits]];
1116        rgba[1] += d->gammatab[d->green[bits]];
1117        rgba[2] += d->gammatab[d->blue[bits]];
1118        rgba[3] += d->alpha[bits];
1119    }
1120    else
1121    {
1122        rgba[0] += d->gammatab[((bits & d->rmask) >> d->rright) << d->rleft];
1123        rgba[1] += d->gammatab[((bits & d->gmask) >> d->gright) << d->gleft];
1124        rgba[2] += d->gammatab[((bits & d->bmask) >> d->bright) << d->bleft];
1125        rgba[3] += ((bits & d->amask) >> d->aright) << d->aleft;
1126    }
1127}
1128
1129/*
1130 * No dithering
1131 */
1132static void init_no_dither(int line)
1133{
1134    ;
1135}
1136
1137static unsigned int get_no_dither(void)
1138{
1139    return 0x80;
1140}
1141
1142static void increment_no_dither(void)
1143{
1144    return;
1145}
1146
1147/*
1148 * Floyd-Steinberg dithering
1149 */
1150static void init_fstein_dither(int line)
1151{
1152    ;
1153}
1154
1155static unsigned int get_fstein_dither(void)
1156{
1157    return 0x80;
1158}
1159
1160static void increment_fstein_dither(void)
1161{
1162    return;
1163}
1164
1165/*
1166 * Ordered 2 dithering
1167 */
1168static unsigned int const *ordered2_table;
1169static unsigned int ordered2_index;
1170
1171static void init_ordered2_dither(int line)
1172{
1173    static unsigned int const dither2x2[] =
1174    {
1175        0x00, 0x80,
1176        0xc0, 0x40,
1177    };
1178
1179    ordered2_table = dither2x2 + (line % 2) * 2;
1180    ordered2_index = 0;
1181}
1182
1183static unsigned int get_ordered2_dither(void)
1184{
1185    return ordered2_table[ordered2_index];
1186}
1187
1188static void increment_ordered2_dither(void)
1189{
1190    ordered2_index = (ordered2_index + 1) % 2;
1191}
1192
1193/*
1194 * Ordered 4 dithering
1195 */
1196/*static int dither4x4[] = { 5,  0,  1,  6,
1197                          -1, -6, -5,  2,
1198                          -2, -7, -8,  3,
1199                           4, -3, -4, -7};*/
1200static unsigned int const *ordered4_table;
1201static unsigned int ordered4_index;
1202
1203static void init_ordered4_dither(int line)
1204{
1205    static unsigned int const dither4x4[] =
1206    {
1207        0x00, 0x80, 0x20, 0xa0,
1208        0xc0, 0x40, 0xe0, 0x60,
1209        0x30, 0xb0, 0x10, 0x90,
1210        0xf0, 0x70, 0xd0, 0x50
1211    };
1212
1213    ordered4_table = dither4x4 + (line % 4) * 4;
1214    ordered4_index = 0;
1215}
1216
1217static unsigned int get_ordered4_dither(void)
1218{
1219    return ordered4_table[ordered4_index];
1220}
1221
1222static void increment_ordered4_dither(void)
1223{
1224    ordered4_index = (ordered4_index + 1) % 4;
1225}
1226
1227/*
1228 * Ordered 8 dithering
1229 */
1230static unsigned int const *ordered8_table;
1231static unsigned int ordered8_index;
1232
1233static void init_ordered8_dither(int line)
1234{
1235    static unsigned int const dither8x8[] =
1236    {
1237        0x00, 0x80, 0x20, 0xa0, 0x08, 0x88, 0x28, 0xa8,
1238        0xc0, 0x40, 0xe0, 0x60, 0xc8, 0x48, 0xe8, 0x68,
1239        0x30, 0xb0, 0x10, 0x90, 0x38, 0xb8, 0x18, 0x98,
1240        0xf0, 0x70, 0xd0, 0x50, 0xf8, 0x78, 0xd8, 0x58,
1241        0x0c, 0x8c, 0x2c, 0xac, 0x04, 0x84, 0x24, 0xa4,
1242        0xcc, 0x4c, 0xec, 0x6c, 0xc4, 0x44, 0xe4, 0x64,
1243        0x3c, 0xbc, 0x1c, 0x9c, 0x34, 0xb4, 0x14, 0x94,
1244        0xfc, 0x7c, 0xdc, 0x5c, 0xf4, 0x74, 0xd4, 0x54,
1245    };
1246
1247    ordered8_table = dither8x8 + (line % 8) * 8;
1248    ordered8_index = 0;
1249}
1250
1251static unsigned int get_ordered8_dither(void)
1252{
1253    return ordered8_table[ordered8_index];
1254}
1255
1256static void increment_ordered8_dither(void)
1257{
1258    ordered8_index = (ordered8_index + 1) % 8;
1259}
1260
1261/*
1262 * Random dithering
1263 */
1264static void init_random_dither(int line)
1265{
1266    ;
1267}
1268
1269static unsigned int get_random_dither(void)
1270{
1271    return cucul_rand(0x00, 0xff);
1272}
1273
1274static void increment_random_dither(void)
1275{
1276    return;
1277}
1278
1279#if !defined(_DOXYGEN_SKIP_ME)
1280int _cucul_init_dither(void)
1281{
1282    unsigned int v, s, h;
1283
1284    /* These ones are constant */
1285    lookup_colors[0] = CUCUL_COLOR_BLACK;
1286    lookup_colors[1] = CUCUL_COLOR_DARKGRAY;
1287    lookup_colors[2] = CUCUL_COLOR_LIGHTGRAY;
1288    lookup_colors[3] = CUCUL_COLOR_WHITE;
1289
1290    /* These ones will be overwritten */
1291    lookup_colors[4] = CUCUL_COLOR_MAGENTA;
1292    lookup_colors[5] = CUCUL_COLOR_LIGHTMAGENTA;
1293    lookup_colors[6] = CUCUL_COLOR_RED;
1294    lookup_colors[7] = CUCUL_COLOR_LIGHTRED;
1295
1296    for(v = 0; v < LOOKUP_VAL; v++)
1297        for(s = 0; s < LOOKUP_SAT; s++)
1298            for(h = 0; h < LOOKUP_HUE; h++)
1299    {
1300        int i, distbg, distfg, dist;
1301        int val, sat, hue;
1302        unsigned char outbg, outfg;
1303
1304        val = 0xfff * v / (LOOKUP_VAL - 1);
1305        sat = 0xfff * s / (LOOKUP_SAT - 1);
1306        hue = 0xfff * h / (LOOKUP_HUE - 1);
1307
1308        /* Initialise distances to the distance between pure black HSV
1309         * coordinates and our white colour (3) */
1310        outbg = outfg = 3;
1311        distbg = distfg = HSV_DISTANCE(0, 0, 0, 3);
1312
1313        /* Calculate distances to eight major colour values and store the
1314         * two nearest points in our lookup table. */
1315        for(i = 0; i < 8; i++)
1316        {
1317            dist = HSV_DISTANCE(hue, sat, val, i);
1318            if(dist <= distbg)
1319            {
1320                outfg = outbg;
1321                distfg = distbg;
1322                outbg = i;
1323                distbg = dist;
1324            }
1325            else if(dist <= distfg)
1326            {
1327                outfg = i;
1328                distfg = dist;
1329            }
1330        }
1331
1332        hsv_distances[v][s][h] = (outfg << 4) | outbg;
1333    }
1334
1335    return 0;
1336}
1337
1338int _cucul_end_dither(void)
1339{
1340    return 0;
1341}
1342#endif /* _DOXYGEN_SKIP_ME */
1343
1344
Note: See TracBrowser for help on using the repository browser.