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

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