The Developer Connection…ice Driver Kit for OS/2 3/DEV3-D1.ISO/source/gbmsrc/gbm/gbmhist.c

C/C++ Source or Header | 1993-02-11 | 4.4 KB | 199 lines

/*

GBMHIST.C  Histogram/Frequency-of-use method of colour reduction

*/

/*...sincludes:0:*/
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include "standard.h"
#include "gbm.h"

/*...vgbm\46\h:0:*/
/*...e*/

/*...sgbm_hist:0:*/
/*
Determine the n_cols_wanted most frequently used colours from 24 bit data.
Can be a problem since potentially 256*256*256 possible unique colours.
Initially 8 bits green, 8 bits red, and 8 bits blue significant.
When number of colours exceeds a limit number of bits of blue reduced by 1.
Next time red, next time green, ...
Sort most n_cols_wanted most frequently used colour in order of use.
Put these in the returned palette.
Map colours from n_cols_wanted exactly to colours in palette.
For other colours, map them to the closest in the palette.
*/

#define    N_COLS    2049
#define    N_HASH    5191
#define    HASH(r,g,b)    (word) ( (((r)+(g))*((g)+(b))*((b)+(r))) % N_HASH )

typedef struct { byte b, g, r; dword freq; byte nearest; } FREQ;

BOOLEAN gbm_hist(
    GBM *gbm, byte *data24,
    GBMRGB gbmrgb [],
    byte *data8,
    int n_cols_wanted,
    byte rm, byte gm, byte bm
    )
    {
    int stride24 = ((gbm -> w * 3 + 3) & ~3);
    int step24 = stride24 - gbm -> w * 3;
    int stride8 = ((gbm -> w + 3) & ~3);
    int step8 = stride8 - gbm -> w;
    FREQ *f;
    word *ht;
    int i, x, y, n_cols;

    /* Frequency table */

    if ( (f = malloc(N_COLS * sizeof(FREQ))) == NULL )
        return ( FALSE );

    /* Hash table, holding 0xffff for unused, index into f if used */

    if ( (ht = malloc(N_HASH * sizeof(word))) == NULL )
        {
        free(f);
        return ( FALSE );
        }

    for ( ;; )
        {
        byte *p = data24;
        BOOLEAN notfull = TRUE;

        n_cols = 0;
        memset(ht, 0xff, N_HASH * sizeof(word));
        for ( y = 0; notfull && y < gbm -> h; y++, p += step24 )
            for ( x = 0; notfull && x < gbm -> w; x++ )
/*...sanalyse pixel:32:*/
{
byte b = (byte) (*p++ & bm);
byte g = (byte) (*p++ & gm);
byte r = (byte) (*p++ & rm);
word hc = HASH(r,g,b);
word inx;

for ( ;; )
    {
    inx = ht [hc];
    if ( inx == 0xffff || (f [inx].r == r && f [inx].g == g && f [inx].b == b) )
        break;
    if ( ++hc == N_HASH ) hc = 0;
    }

/* Note: loop will always be broken out of */
/* We don't allow ht to fill up above half full */

if ( inx == 0xffff )
    /* Not found in hash table */
    {
    f [n_cols].freq = (dword) 1;
    f [n_cols].b    = b;
    f [n_cols].g    = g;
    f [n_cols].r    = r;
    ht [hc] = n_cols;
    if ( ++n_cols == N_COLS )
        notfull = FALSE;
    }
else
    /* Found in hash table */
    /* update index inx */
    f [inx].freq++;
}
/*...e*/

        if ( notfull )
            break;

        if ( gm > rm )
            gm <<= 1;
        else if ( rm > bm )
            rm <<= 1;
        else
            bm <<= 1;
        }

    /* Above loop will always be exited as if masks get rough
       enough, ultimately number of unique colours < N_COLS */

    /* Now find the n_cols_wanted most frequently used ones */

    for ( i = 0; i < n_cols_wanted && i < n_cols; i++ )
        {
        int j, max_j;
        dword max_freq = 0;

        for ( j = 0; j < n_cols; j++ )
            if ( f [j].freq > max_freq )
                {
                max_j    = j;
                max_freq = f [j].freq;
                }
        f [max_j].nearest = (byte) i;
        f [max_j].freq = (dword) 0; /* Prevent later use of f [max_j] */
        gbmrgb [i].b = f [max_j].b;
        gbmrgb [i].g = f [max_j].g;
        gbmrgb [i].r = f [max_j].r;
        }

    /* For the rest, find the closest one in the first n_cols_wanted */

    for ( i = 0; i < n_cols; i++ )
        if ( f [i].freq != (dword) 0 )
            {
            int j, min_j;
            int min_dist = 3*256*256;

            for ( j = 0; j < n_cols_wanted; j++ )
                {
                int db = (int) f [i].b - (int) gbmrgb [j].b;
                int dg = (int) f [i].g - (int) gbmrgb [j].g;
                int dr = (int) f [i].r - (int) gbmrgb [j].r;
                int dist = dr*dr + dg*dg + db*db;

                if ( dist < min_dist )
                    {
                    min_dist = dist;
                    min_j    = j;
                    }
                }
            f [i].nearest = (byte) min_j;
            }

    /* Now transform the image data */

    for ( y = 0; y < gbm -> h; y++, data24 += step24, data8 += step8 )
        for ( x = 0; x < gbm -> w; x++ )
            {
            byte b = (*data24++ & bm);
            byte g = (*data24++ & gm);
            byte r = (*data24++ & rm);
            word hc = HASH(r,g,b);
            word inx;

            for ( ;; )
                {
                inx = ht [hc];
                if ( f [inx].r == r && f [inx].g == g && f [inx].b == b )
                    break;
                if ( ++hc == N_HASH ) hc = 0;
                }

            *data8++ = f [inx].nearest;
            }

    free(ht);
    free(f);

    return ( TRUE );
    }
/*...e*/