From 1fd361a1ea06e44286c213ca1f814f49306fdc43 Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sat, 19 Aug 2006 03:12:28 +0000 Subject: Create Subversion repository git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- lib/libpammap.c | 662 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 662 insertions(+) create mode 100644 lib/libpammap.c (limited to 'lib/libpammap.c') diff --git a/lib/libpammap.c b/lib/libpammap.c new file mode 100644 index 00000000..9e90ade0 --- /dev/null +++ b/lib/libpammap.c @@ -0,0 +1,662 @@ +/****************************************************************************** + libpammap.c +******************************************************************************* + + These are functions that deal with tuple hashes and tuple tables. + + Both tuple hashes and tuple tables let you associate an arbitrary + integer with a tuple value. A tuple hash lets you look up the one + integer value (if any) associated with a given tuple value, having + the low memory and execution time characteristics of a hash table. + A tuple table lets you scan all the values, being a table of elements + that consist of an ordered pair of a tuple value and integer. + +******************************************************************************/ + +#include + +#include "pm_c_util.h" +#include "mallocvar.h" +#include "pam.h" +#include "pammap.h" + + +#define HASH_SIZE 20023 + +unsigned int +pnm_hashtuple(struct pam * const pamP, tuple const tuple) { +/*---------------------------------------------------------------------------- + Return the hash value of the tuple 'tuple' -- i.e. an index into a hash + table. +-----------------------------------------------------------------------------*/ + int i; + unsigned int hash; + const unsigned int hash_factor[] = {33023, 30013, 27011}; + + hash = 0; /* initial value */ + for (i = 0; i < MIN(pamP->depth, 3); ++i) { + hash += tuple[i] * hash_factor[i]; /* May overflow */ + } + hash %= HASH_SIZE; + return hash; +} + + + + +tuplehash +pnm_createtuplehash(void) { +/*---------------------------------------------------------------------------- + Create an empty tuple hash -- i.e. a hash table of zero length hash chains. +-----------------------------------------------------------------------------*/ + tuplehash retval; + unsigned int i; + + MALLOCARRAY(retval, HASH_SIZE); + + if (retval == NULL) + pm_error("Out of memory allocating tuple hash of size %u", + HASH_SIZE); + + for (i = 0; i < HASH_SIZE; ++i) + retval[i] = NULL; + + return retval; +} + + + +void +pnm_destroytuplehash(tuplehash const tuplehash) { + + int i; + + /* Free the chains */ + + for (i = 0; i < HASH_SIZE; ++i) { + struct tupleint_list_item * p; + struct tupleint_list_item * next; + + /* Walk this chain, freeing each element */ + for (p = tuplehash[i]; p; p = next) { + next = p->next; + + free(p); + } + } + + /* Free the table of chains */ + free(tuplehash); +} + + + + +static struct tupleint_list_item * +allocTupleIntListItem(struct pam * const pamP) { + + + /* This is complicated by the fact that the last element of a + tupleint_list_item is of variable length, because the last element + of _it_ is of variable length + */ + struct tupleint_list_item * retval; + + unsigned int const size = + sizeof(*retval) - sizeof(retval->tupleint.tuple) + + pamP->depth * sizeof(sample); + + retval = (struct tupleint_list_item *) malloc(size); + + return retval; +} + + + +void +pnm_addtotuplehash(struct pam * const pamP, + tuplehash const tuplehash, + tuple const tupletoadd, + int const value, + int * const fitsP) { +/*---------------------------------------------------------------------------- + Add a tuple value to the hash -- assume it isn't already there. + + Allocate new space for the tuple value and the hash chain element. + + If we can't allocate space for the new hash chain element, don't + change anything and return *fitsP = FALSE; +-----------------------------------------------------------------------------*/ + struct tupleint_list_item * const listItemP = allocTupleIntListItem(pamP); + if (listItemP == NULL) + *fitsP = FALSE; + else { + unsigned int const hashvalue = pnm_hashtuple(pamP, tupletoadd); + + *fitsP = TRUE; + + pnm_assigntuple(pamP, listItemP->tupleint.tuple, tupletoadd); + listItemP->tupleint.value = value; + listItemP->next = tuplehash[hashvalue]; + tuplehash[hashvalue] = listItemP; + } +} + + + +void +pnm_lookuptuple(struct pam * const pamP, + const tuplehash tuplehash, + const tuple searchval, + int * const foundP, + int * const retvalP) { + + unsigned int const hashvalue = pnm_hashtuple(pamP, searchval); + struct tupleint_list_item * p; + struct tupleint_list_item * found; + + found = NULL; /* None found yet */ + for (p = tuplehash[hashvalue]; p && !found; p = p->next) + if (pnm_tupleequal(pamP, p->tupleint.tuple, searchval)) { + found = p; + } + + if (found) { + *foundP = TRUE; + *retvalP = found->tupleint.value; + } else + *foundP = FALSE; +} + + + +static void +addColorOccurrenceToHash(tuple const color, + tuplehash const tuplefreqhash, + struct pam * const pamP, + unsigned int const maxsize, + unsigned int * const sizeP, + bool * const fullP) { + + unsigned int const hashvalue = pnm_hashtuple(pamP, color); + + struct tupleint_list_item *p; + + for (p = tuplefreqhash[hashvalue]; + p && !pnm_tupleequal(pamP, p->tupleint.tuple, color); + p = p->next); + + if (p) { + /* It's in the hash; just tally one more occurence */ + ++p->tupleint.value; + *fullP = FALSE; + } else { + /* It's not in the hash yet, so add it (if allowed) */ + ++(*sizeP); + if (maxsize > 0 && *sizeP > maxsize) + *fullP = TRUE; + else { + *fullP = FALSE; + p = allocTupleIntListItem(pamP); + if (p == NULL) + pm_error("out of memory computing hash table"); + pnm_assigntuple(pamP, p->tupleint.tuple, color); + p->tupleint.value = 1; + p->next = tuplefreqhash[hashvalue]; + tuplefreqhash[hashvalue] = p; + } + } +} + + + +void +pnm_addtuplefreqoccurrence(struct pam * const pamP, + tuple const value, + tuplehash const tuplefreqhash, + int * const firstOccurrenceP) { + + unsigned int const hashvalue = pnm_hashtuple(pamP, value); + + struct tupleint_list_item * p; + + for (p = tuplefreqhash[hashvalue]; + p && !pnm_tupleequal(pamP, p->tupleint.tuple, value); + p = p->next); + + if (p) { + /* It's in the hash; just tally one more occurence */ + ++p->tupleint.value; + *firstOccurrenceP = FALSE; + } else { + struct tupleint_list_item * p; + + /* It's not in the hash yet, so add it */ + *firstOccurrenceP = TRUE; + + p = allocTupleIntListItem(pamP); + if (p == NULL) + pm_error("out of memory computing hash table"); + + pnm_assigntuple(pamP, p->tupleint.tuple, value); + p->tupleint.value = 1; + p->next = tuplefreqhash[hashvalue]; + tuplefreqhash[hashvalue] = p; + } +} + + + +static void +computehashrecoverable(struct pam * const pamP, + tuple ** const tupleArray, + unsigned int const maxsize, + sample const newMaxval, + unsigned int * const sizeP, + tuplehash * const tuplefreqhashP, + tuple ** const rowbufferP, + tuple * const colorP) { +/*---------------------------------------------------------------------------- + This is computetuplefreqhash(), only it leaves a trail so that if it + happens to longjmp out because of a failed memory allocation, the + setjmp'er can cleanup whatever it had done so far. +-----------------------------------------------------------------------------*/ + unsigned int row; + struct pam freqPam; + bool full; + + freqPam = *pamP; + freqPam.maxval = newMaxval; + + *tuplefreqhashP = pnm_createtuplehash(); + *sizeP = 0; /* initial value */ + + *rowbufferP = pnm_allocpamrow(pamP); + + *colorP = pnm_allocpamtuple(&freqPam); + + full = FALSE; /* initial value */ + + /* Go through the entire raster, building a hash table of + tuple values. + */ + for (row = 0; row < pamP->height && !full; ++row) { + int col; + const tuple * tuplerow; /* The row of tuples we are processing */ + + if (tupleArray) + tuplerow = tupleArray[row]; + else { + pnm_readpamrow(pamP, *rowbufferP); + tuplerow = *rowbufferP; + } + for (col = 0; col < pamP->width && !full; ++col) { + pnm_scaletuple(pamP, *colorP, tuplerow[col], freqPam.maxval); + addColorOccurrenceToHash( + *colorP, *tuplefreqhashP, &freqPam, maxsize, sizeP, &full); + } + } + + pnm_freepamtuple(*colorP); *colorP = NULL; + pnm_freepamrow(*rowbufferP); *rowbufferP = NULL; + + if (full) { + pnm_destroytuplehash(*tuplefreqhashP); + *tuplefreqhashP = NULL; + } +} + + + +static tuplehash +computetuplefreqhash(struct pam * const pamP, + tuple ** const tupleArray, + unsigned int const maxsize, + sample const newMaxval, + unsigned int * const sizeP) { +/*---------------------------------------------------------------------------- + Compute a tuple frequency hash from a PAM. This is a hash that gives + you the number of times a given tuple value occurs in the PAM. You can + supply the input PAM in one of two ways: + + 1) a two-dimensional array of tuples tupleArray[][]; In this case, + 'tupleArray' is non-NULL. + + 2) an open PAM file, positioned to the raster. In this case, + 'tupleArray' is NULL. *pamP contains the file descriptor. + + We return with the file still open and its position undefined. + + In either case, *pamP contains parameters of the tuple array. + + Return the number of unique tuple values found as *sizeP. + + However, if the number of unique tuple values is greater than 'maxsize', + return a null return value and *sizeP undefined. + + The tuple values that index the hash are scaled to a new maxval of + 'newMaxval'. E.g. if the input has maxval 100 and 'newMaxval' is + 50, and a particular tuple has sample value 50, it would be counted + as sample value 25 in the hash. +-----------------------------------------------------------------------------*/ + tuplehash tuplefreqhash; + tuple * rowbuffer; /* malloc'ed */ + /* Buffer for a row read from the input file; undefined (but still + allocated) if input is not from a file. + */ + tuple color; + /* The color currently being added, scaled to the new maxval */ + jmp_buf jmpbuf; + jmp_buf * origJmpbufP; + + /* Initialize to "none" for purposes of error recovery */ + tuplefreqhash = NULL; + rowbuffer = NULL; + color = NULL; + + if (setjmp(jmpbuf) == 0) { + pm_setjmpbufsave(&jmpbuf, &origJmpbufP); + computehashrecoverable(pamP, tupleArray, maxsize, newMaxval, sizeP, + &tuplefreqhash, &rowbuffer, &color); + pm_setjmpbuf(origJmpbufP); + } else { + if (color) + pnm_freepamtuple(color); + if (rowbuffer) + pnm_freepamrow(rowbuffer); + if (tuplefreqhash) + pnm_destroytuplehash(tuplefreqhash); + pm_longjmp(); + } + return tuplefreqhash; +} + + + +tuplehash +pnm_computetuplefreqhash(struct pam * const pamP, + tuple ** const tupleArray, + unsigned int const maxsize, + unsigned int * const sizeP) { +/*---------------------------------------------------------------------------- + Compute the tuple frequency hash for the tuple array tupleArray[][]. +-----------------------------------------------------------------------------*/ + return computetuplefreqhash(pamP, tupleArray, maxsize, pamP->maxval, + sizeP); +} + + + +tupletable +pnm_alloctupletable(const struct pam * const pamP, + unsigned int const size) { + + tupletable retval; + + if (UINT_MAX / sizeof(struct tupleint) < size) + pm_error("size %u is too big for arithmetic", size); + else { + unsigned int const mainTableSize = size * sizeof(struct tupleint *); + unsigned int const tupleIntSize = + sizeof(struct tupleint) - sizeof(sample) + + pamP->depth * sizeof(sample); + + /* To save the enormous amount of time it could take to allocate + each individual tuple, we do a trick here and allocate everything + as a single malloc block and suballocate internally. + */ + if ((UINT_MAX - mainTableSize) / tupleIntSize < size) + pm_error("size %u is too big for arithmetic", size); + else { + void * pool; + unsigned int i; + + pool = malloc(mainTableSize + size * tupleIntSize); + + retval = (tupletable) pool; + + for (i = 0; i < size; ++i) + retval[i] = (struct tupleint *) + ((char*)pool + mainTableSize + i * tupleIntSize); + } + } + return retval; +} + + + +void +pnm_freetupletable(struct pam * const pamP, + tupletable const tupletable) { + + /* Note that the address 'tupletable' is, to the operating system, + the address of a larger block of memory that contains not only + tupletable, but all the samples to which it points (e.g. + tupletable[0].tuple[0]) + */ + + free(tupletable); +} + + + +void +pnm_freetupletable2(struct pam * const pamP, + tupletable2 const tupletable) { + + pnm_freetupletable(pamP, tupletable.table); +} + + + +static tupletable +tuplehashtotable(const struct pam * const pamP, + tuplehash const tuplehash, + unsigned int const allocsize) { +/*---------------------------------------------------------------------------- + Create a tuple table containing the info from a tuple hash. Allocate + space in the table for 'allocsize' elements even if there aren't that + many tuple values in the input hash. That's so the caller has room + for expansion. + + Caller must ensure that 'allocsize' is at least as many tuple values + as there are in the input hash. + + We allocate new space for all the table contents; there are no pointers + in the table to tuples or anything else in existing space. +-----------------------------------------------------------------------------*/ + tupletable tupletable; + + tupletable = pnm_alloctupletable(pamP, allocsize); + + if (tupletable != NULL) { + unsigned int i, j; + /* Loop through the hash table. */ + j = 0; + for (i = 0; i < HASH_SIZE; ++i) { + /* Walk this hash chain */ + struct tupleint_list_item * p; + for (p = tuplehash[i]; p; p = p->next) { + assert(j < allocsize); + tupletable[j]->value = p->tupleint.value; + pnm_assigntuple(pamP, tupletable[j]->tuple, p->tupleint.tuple); + ++j; + } + } + } + return tupletable; +} + + + +tupletable +pnm_tuplehashtotable(const struct pam * const pamP, + tuplehash const tuplehash, + unsigned int const allocsize) { + + tupletable tupletable; + + tupletable = tuplehashtotable(pamP, tuplehash, allocsize); + + if (tupletable == NULL) + pm_error("out of memory generating tuple table"); + + return tupletable; +} + + + +tuplehash +pnm_computetupletablehash(struct pam * const pamP, + tupletable const tupletable, + unsigned int const tupletableSize) { +/*---------------------------------------------------------------------------- + Create a tuple hash containing indices into the tuple table + 'tupletable'. The hash index for the hash is the value of a tuple; + the hash value is the tuple table index for the element in the + tuple table that contains that tuple value. + + Assume there are no duplicate tuple values in the tuple table. + + We allocate space for the main hash table and all the elements of the + hash chains. +-----------------------------------------------------------------------------*/ + tuplehash tupletablehash; + unsigned int i; + bool fits; + + tupletablehash = pnm_createtuplehash(); + + fits = TRUE; /* initial assumption */ + for (i = 0; i < tupletableSize && fits; ++i) { + pnm_addtotuplehash(pamP, tupletablehash, + tupletable[i]->tuple, i, &fits); + } + if (!fits) { + pnm_destroytuplehash(tupletablehash); + pm_error("Out of memory computing tuple hash from tuple table"); + } + return tupletablehash; +} + + + +tupletable +pnm_computetuplefreqtable2(struct pam * const pamP, + tuple ** const tupleArray, + unsigned int const maxsize, + sample const newMaxval, + unsigned int * const countP) { +/*---------------------------------------------------------------------------- + Compute a tuple frequency table from a PAM image. This is an + array that tells how many times each tuple value occurs in the + image. + + Except for the format of the output, this function is the same as + computetuplefreqhash(). + + If there are more than 'maxsize' unique tuple values in tupleArray[][], + give up. + + Return the array in newly malloc'ed storage. Allocate space for + 'maxsize' entries even if there aren't that many distinct tuple + values in tupleArray[]. That's so the caller has room for + expansion. + + If 'maxsize' is zero, allocate exactly as much space as there are + distinct tuple values in tupleArray[], and don't give up no matter + how many tuple values we find (except, of course, we abort if we + can't get enough memory). + + Return the number of unique tuple values in tupleArray[][] as + *countP. + + + Scale the tuple values to a new maxval of 'newMaxval' before + processing them. E.g. if the input has maxval 100 and 'newMaxval' + is 50, and a particular tuple has sample value 50, it would be + listed as sample value 25 in the output table. This makes the + output table smaller and the processing time less. +-----------------------------------------------------------------------------*/ + tuplehash tuplefreqhash; + tupletable tuplefreqtable; + unsigned int uniqueCount; + + tuplefreqhash = computetuplefreqhash(pamP, tupleArray, maxsize, + newMaxval, &uniqueCount); + if (tuplefreqhash == NULL) + tuplefreqtable = NULL; + else { + unsigned int tableSize = (maxsize == 0 ? uniqueCount : maxsize); + assert(tableSize >= uniqueCount); + tuplefreqtable = tuplehashtotable(pamP, tuplefreqhash, tableSize); + pnm_destroytuplehash(tuplefreqhash); + if (tuplefreqtable == NULL) + pm_error("Out of memory generating tuple table"); + } + *countP = uniqueCount; + + return tuplefreqtable; +} + + + +tupletable +pnm_computetuplefreqtable(struct pam * const pamP, + tuple ** const tupleArray, + unsigned int const maxsize, + unsigned int * const sizeP) { + + return pnm_computetuplefreqtable2(pamP, tupleArray, maxsize, pamP->maxval, + sizeP); +} + + + +char* +pam_colorname(struct pam * const pamP, + tuple const color, + enum colornameFormat const format) { + + unsigned int r, g, b; + FILE* f; + static char colorname[200]; + + r = pnm_scalesample(color[PAM_RED_PLANE], pamP->maxval, 255); + g = pnm_scalesample(color[PAM_GRN_PLANE], pamP->maxval, 255); + b = pnm_scalesample(color[PAM_BLU_PLANE], pamP->maxval, 255); + + f = pm_openColornameFile(NULL, format == PAM_COLORNAME_ENGLISH); + if (f != NULL) { + unsigned int best_diff; + bool done; + + best_diff = 32767; + done = FALSE; + while (!done) { + struct colorfile_entry const ce = pm_colorget(f); + if (ce.colorname) { + unsigned int const this_diff = + abs((int)r - (int)ce.r) + + abs((int)g - (int)ce.g) + + abs((int)b - (int)ce.b); + + if (this_diff < best_diff) { + best_diff = this_diff; + strcpy(colorname, ce.colorname); + } + } else + done = TRUE; + } + fclose(f); + if (best_diff != 32767 && + (best_diff == 0 || format == PAM_COLORNAME_ENGLISH)) + return colorname; + } + + /* Color lookup failed, but caller is willing to take an X11-style + hex specifier, so return that. + */ + sprintf(colorname, "#%02x%02x%02x", r, g, b); + return colorname; +} -- cgit 1.4.1