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

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