Small Lookup Table for Large Integers

I want to make a quick, relatively small lookup table, but with a large input range: -Input: 32bit Value max. (a 32bit color value) -Output: 8bit Index max. (index to a table)

Something like the code below. (If more than 256 values are indexed, the index is just going to be 0)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

static uint8_t getIndx(uint32_t value);
static uint8_t **indx;
static uint8_t count = 0;

int main(void) {
  // set up the indx
  const uint32_t size = 0xFFFF;  // for demonstrative purposes not even nearly as large as wished to be (0xFFFFFFFF) plus my for loop below would get in trouble, I think
  indx = (uint8_t**)malloc(sizeof(uint8_t*) * size);
  if(indx == NULL) {
    printf("could not allocate memory\n");
    return 0;
  }
  for(int i = 0; i < size + 1; i++) {
    indx[i] = NULL;
  }

  printf("%d\n", getIndx(111));
  printf("%d\n", getIndx(222));
  printf("%d\n", getIndx(333));
  printf("%d\n", getIndx(111));
  printf("%d\n", getIndx(222));
  printf("%d\n", getIndx(333));

  return 0;
}

static uint8_t getIndx(uint32_t value) {
  if(indx[value] == NULL) {
    if(count > 255) return 0;
    indx[value] = (uint8_t*)malloc(sizeof(uint8_t));
    *indx[value] = count;
    count++;
  }
  return *(indx[value]);
}

The output is:

0
1
2
0
1
2

No matter what I think of, I always end up with something like that. With an input range of 32bit (4294967296 states) I would need to allocate way too much memory to only get 256 possible outputs. And forming 256 if else, inside a for loop or not, is also not what I want.

Is there some method that is quick, either a table or not which in the end has the same function, that I have not yet heard about?

Many thanks in advance!

You can use a hash table to map the 32-bit values to the look-up table indices. The length of the hash table should be significantly longer than the look-up table to reduce the chance of hash collisions.

The following example uses a linear search of the hash table starting at the hash value derived from the input value until a matching entry is found or an empty hash table is found. If the input value is not found, and there is room in the look-up table and room in the hash table (which there should be since it is longer than the look-up table), the input value is added to the look-up table and the hash table is updated. It uses a hash table four times the size of the look-up table.

The example does two passes with the same pseudo-random sequence in each pass. The first pass should mostly fill up the look-up table and update the hash table. The second pass shouldn't make any more changes to the look-up table or hash table because it is just repeating the first sequence.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>

struct hash_index {
  uint8_t index;
  char used;
};

#define HASHBITS  10
#define HASHSIZE  (1U << HASHBITS)
#define HASHMASK  (HASHSIZE - 1)
#define LOOKUPSIZE  256U

static uint8_t getIndx(uint32_t value);
static uint32_t lookup[LOOKUPSIZE];
static struct hash_index hashtab[HASHSIZE];
static unsigned int count = 0;
static unsigned int tot_collisions = 0;
static unsigned int max_collisions = 0;
static unsigned int hash_used = 0;

int main(void) {
  int pass;
  unsigned int i;
  uint32_t value;
  uint8_t index;
  unsigned int successes;
  unsigned int failures;
  int ok;

  printf("Lookup size: %u, Hash size: %u\n", LOOKUPSIZE, HASHSIZE);
  for (pass = 1; pass <= 2; pass++) {
    successes = 0;
    failures = 0;
    tot_collisions = 0;
    max_collisions = 0;
    /* Not resetting hash_used because it shouldn't change after first pass. */
    printf("\nPass %d, currently used hashes: %u\n\n", pass, hash_used);
    srand(1);
    for (i = 0; i < 260; i++) {
      static const char * const outcomes[2] = {"FAIL", "OK"};
      value = rand();
      index = getIndx(value);
      ok = lookup[index] == value;
      printf("%" PRIu32 " -> %" PRIu8 " (%s)\n", value, index, outcomes[ok]);
      if (ok) {
        successes++;
      } else {
        failures++;
      }
    }
    printf("\nSuccesses: %u, Failures: %u\n", successes, failures);
    printf("Used hashes: %u, Total collisions: %u, Max collisions: %u\n\n",
           hash_used, tot_collisions, max_collisions);
  }

  return 0;
}

static uint8_t getIndx(uint32_t value) {
  unsigned int initial_hash;
  unsigned int hash;
  unsigned int collisions = 0;
  uint8_t index;

  /*
   * Search for value using hash table, starting at position hashed from value.
   *
   * The hash table is longer than the maximum number of used entries,
   * so we should always be able to find an unused entry in the hash table.
   */
  initial_hash = ((value * UINT32_C(0x61c88647)) >> (32 - HASHBITS)) & HASHMASK;
  for (hash = initial_hash;
       collisions < HASHSIZE && hashtab[hash].used;
       hash = (hash + 1) & HASHMASK) {
    /*
     * This hash table entry is used.  Get the corresponding index in the
     * main lookup table to check if the value matches.
     */
    index = hashtab[hash].index;
    if (lookup[index] == value) {
      /* Matching value found.  Return its index in the main table. */
      return index;
    }
    /* Count hash collisions and total hash collisions. */
    collisions++;
    tot_collisions++;
    if (max_collisions < collisions) {
      /* Update max hash collisions for diagnostics. */
      max_collisions = collisions;
    }
  }
  /* Value not found. */
  if (count < LOOKUPSIZE && collisions < HASHSIZE) {
    /*
     * There is room in the main lookup table for the new value
     * and room in the hash table.  The index of the new value in the
     * main lookup table will be the current count, which will be incremented.
     */
    index = count++;
    /*
     * Add value to main lookup table,
     * add index in main lookup table to hash table,
     * and return the index in the main lookup table.
     */
    lookup[index] = value;
    hashtab[hash].index = index;
    hashtab[hash].used = 1;
    hash_used++;  /* Count of used hash table entries for diagnostics. */
    return index;
  }
  /*
   * Value not found and main lookup table is full or hash table is full.
   * Give up.
   */
  return 0;
}

Another approach for dealing with collisions is to make each hash table entry point to a linked list of matching values, but that is more complicated.