key.h

Go to the documentation of this file.

 
#include <stdio.h>
 
#include "common.h"
#include "debug.h"
 
#ifndef RBT_KEY_H_PREFIX_
#error RBT_KEY_H_PREFIX_ is not defined.
#endif // RBT_KEY_H_PREFIX_
 
#ifndef RBT_PIN_T
#error RBT_PIN_T is not defined.
#endif // RBT_PIN_T
 
#ifndef RBT_KEY_SIZE_T
#error RBT_KEY_SIZE_T is not defined.
#endif // RBT_KEY_SIZE_T
 
#ifndef RBT_KEY_SIZE_T_FORMAT
#error RBT_KEY_SIZE_T_FORMAT is not defined.
#endif // RBT_KEY_SIZE_T_FORMAT
 
 
/*
  Typedef these so that they are not lost if the preceding macros are redefined
  for another inclusion.
*/
typedef RBT_PIN_T      RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, pin_t);
typedef RBT_KEY_SIZE_T RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, key_size_t);
 
#undef RBT_FPRINT_BITS
#define RBT_FPRINT_BITS           RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, fprint_bits)
 
#undef RBT_COMMON_BIT_PREFIX_LEN
#define RBT_COMMON_BIT_PREFIX_LEN RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, common_bit_prefix_len)
/*
  The conditional definitions may be unnecessary if multiplication by 1 would be
  optimized by the compiler, but it does not hurt and it assures that the more
  efficient method is used.
*/
#undef RBT_PIN_SIZE
#define RBT_PIN_SIZE sizeof(RBT_PIN_T)
#undef RBT_PIN_SIZE_BITS
#define RBT_PIN_SIZE_BITS (RBT_PIN_SIZE * BITS_PER_BYTE)
 
#undef BITS_TO_PINS
#define BITS_TO_PINS(x) DIV_UP(x, RBT_PIN_SIZE_BITS)
 
#undef PINS_TO_BYTES
#define PINS_TO_BYTES(x) ((x) * RBT_PIN_SIZE)
 
#undef BITS_TO_PINS_TO_BYTES
#define BITS_TO_PINS_TO_BYTES(x) PINS_TO_BYTES(BITS_TO_PINS(x))
 
 
 
 
 
 
 
 
 
void
RBT_FPRINT_BITS(FILE * fd, RBT_PIN_T * key, RBT_KEY_SIZE_T n, RBT_KEY_SIZE_T skip)
{
  int i;
  for (i = skip; n > 0; i++,n--)
  {
    while (i >= RBT_PIN_SIZE_BITS)
    {
      i -= RBT_PIN_SIZE_BITS;
      key ++;
    }
    fprintf(fd, "%d", (MOST_SIGNIFICANT_BIT(typeof(key[0])) & (key[0] << i)) > 0);
  }
}
 
 
 
 
 
#undef RBT_DIVMOD
#define RBT_DIVMOD(a,b,c,d) \
c = a / b; \
d = a % b
 
 
 
 
RBT_KEY_SIZE_T
RBT_COMMON_BIT_PREFIX_LEN(
  RBT_PIN_T * a,
  RBT_PIN_T * b,
  RBT_KEY_SIZE_T max
)
{
  RBT_PIN_T c;
  RBT_KEY_SIZE_T length;
 
  length = 0;
 
  while (length < max && * a == * b)
  {
    length += RBT_PIN_SIZE_BITS;
    a ++;
    b ++;
  }
  if (length < max)
  {
    c = *a ^ *b;
#ifdef __GNUC__
    /*
      Make use of the GCC builtins:
      http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
 
      TODO
      At some point check if this is even worth it. Also consider checking
      compatibility of the returned int with RBT_KEY_SIZE_T. Under normal operation
      RBT_KEY_SIZE_T will be able to hold the value, but there may be overhead due
      to conversion between types.
    */
    if (__builtin_types_compatible_p(RBT_PIN_T, unsigned int))
    {
      debug_print("__builtin_clz\n");
      length += (RBT_KEY_SIZE_T) __builtin_clz(c);
    }
    else if (__builtin_types_compatible_p(RBT_PIN_T, unsigned long int))
    {
      debug_print("__builtin_clzl\n");
      length += (RBT_KEY_SIZE_T) __builtin_clzl(c);
    }
    else if (__builtin_types_compatible_p(RBT_PIN_T, unsigned long long int))
    {
      debug_print("__builtin_clzll\n");
      length += (RBT_KEY_SIZE_T) __builtin_clzll(c);
    }
    else
    {
#endif // __GNUC__
//       debug_print("loop\n");
    /*
      The condition above ensures that the length is less than the max, so it
      cannot be exceeded here and there is no need to check before returning it.
 
      The leading 0's represent common bits due to the XOR operation above. The
      previous loop ensures that *a and *b are not identical so there must be
      at least one bit in c. By shifting it left and checking if the value is
      less than MOST_SIGNIFICANT_BIT we can count the leading zeros and thus the
      number of common bits.
    */
    while (c < MOST_SIGNIFICANT_BIT_W(RBT_PIN_T) && length < max)
    {
      c <<= 1;
      length += 1;
    }
    return length;
#ifdef __GNUC__
    }
    return (length > max) ? max : length;
#endif // __GNUC__
  }
  else
  {
    return max;
  }
}