c++ - hashing - Compila el hash de cadena de tiempo

set c++ 11

Question

He leído en algunos lugares diferentes que utilizando los nuevos literales de cadena de C ++ 11 podría ser posible calcular el hash de una cadena en el momento de la compilación. Sin embargo, nadie parece estar listo para salir y decir que será posible o cómo se haría.

• es posible?
• ¿Cómo se vería el operador?

Estoy particularmente interesado en casos de uso como este.

void foo( const std::string& value )
{
   switch( std::hash(value) )
   {
      case "one"_hash: one(); break;
      case "two"_hash: two(); break;
      /*many more cases*/
      default: other(); break;
   }
}

Nota: la función hash del tiempo de compilación no tiene que verse exactamente como lo he escrito. Hice todo lo posible para adivinar cómo sería la solución final, pero meta_hash<"string"_meta>::value también podría ser una solución viable.

Answer 1

Al menos por mi lectura de §7.1.5 / 3 y §5.19, lo siguiente puede ser legítimo:

unsigned constexpr const_hash(char const *input) {
    return *input ?
        static_cast<unsigned int>(*input) + 33 * const_hash(input + 1) :
        5381;
}

Esto parece seguir las reglas básicas en §7.1.5 / 3:

1. La forma es: "expresión de retorno";
2. Su único parámetro es un puntero, que es un tipo escalar y, por lo tanto, un tipo literal.
3. Su retorno es unsigned int, que también es escalar (y, por lo tanto, literal).
4. No hay conversión implícita al tipo de devolución.

Existe alguna duda sobre si las *input implican un valor l ilegal para validar la conversión, y no estoy seguro de entender las reglas en §5.19 / 2/6/2 ¹ y §4 lo suficientemente bien como para estar seguro de eso.

Desde un punto de vista práctico, este código es aceptado por (por ejemplo) g ++, al menos tan atrás como g ++ 4.7.1.

El uso sería algo así como:

switch(std::hash(value)) {
    case const_hash("one"): one(); break;
    case const_hash("two"): two(); break;
    // ...
    default: other(); break;
}

Para cumplir con los requisitos de §5.19 / 2/6/2, quizás tengas que hacer algo como esto:

// one of the `constexpr`s is probably redundant, but I haven''t figure out which.
char constexpr * constexpr v_one = "one"; 

// ....

case const_hash(v_one): one(); break;

1. Estoy usando los números adicionales de ''barra inclinada'' para referirme a los puntos de viñeta no numerados, por lo que este es el segundo punto dentro si el sexto punto de la viñeta es §5.19 / 2. Creo que tendré que hablar con Pete Becker sobre si es posible agregar algún tipo de números / letras / números romanos en la jerarquía para identificar piezas como esta ...

Answer 2

Aquí hay otra implementación de C ++ 11 (basada en la respuesta de @ CygnusX1), que funciona tanto con arreglos constexpr char como con cadenas de tiempo de ejecución:

namespace detail {

    // CRC32 Table (zlib polynomial)
    static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... };

    constexpr uint32_t combine_crc32(size_t idx, const char * str, uint32_t part) {
        return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
    }

    constexpr uint32_t crc32(size_t idx, const char * str) {
        return idx == size_t(-1) ? 
            0xFFFFFFFF : combine_crc32(idx, str, crc32(idx - 1, str));
    }
}

uint32_t ctcrc32(std::string const& str) {
    size_t len = str.size() + 1;
    return detail::crc32(len - 2, str.c_str()) ^ 0xFFFFFFFF;
}

template <size_t len>
constexpr uint32_t ctcrc32(const char (&str)[len]) {
    return detail::crc32(len - 2, str) ^ 0xFFFFFFFF;
}

Necesitas str.size() + 1 porque len en la segunda sobrecarga es strlen(str) + 1 debido al carácter nulo al final.

No agregué una sobrecarga para const char * porque se equivoca con la segunda sobrecarga. Puede agregar fácilmente sobrecargas para const char *, size_t o std::string_view .

Answer 3

Esta es una buena pregunta.

Basado en la respuesta de Jerry Coffin, creé otro que es compatible con std :: hash de Visual Studio 2017.

#include <functional>
#include <cassert>
using namespace std;


constexpr size_t cx_hash(const char* input) {
    size_t hash = sizeof(size_t) == 8 ? 0xcbf29ce484222325 : 0x811c9dc5;
    const size_t prime = sizeof(size_t) == 8 ? 0x00000100000001b3 : 0x01000193;

    while (*input) {
        hash ^= static_cast<size_t>(*input);
        hash *= prime;
        ++input;
    }

    return hash;
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    auto a = cx_hash("test");
    hash<string> func;
    auto b = func("test");
    assert(a == b);

    return 0;
}

https://github.com/manuelgustavo/cx_hash

Answer 4

Este es un intento de resolver el problema de OP lo más exactamente posible.

namespace my_hash {
  template<class>struct hasher;
  template<>
  struct hasher<std::string> {
    std::size_t constexpr operator()(char const *input)const {
      return *input ?
        static_cast<unsigned int>(*input) + 33 * (*this)(input + 1) :
        5381;
    }
    std::size_t operator()( const std::string& str ) const {
      return (*this)(str.c_str());
    }
  };
  template<typename T>
  std::size_t constexpr hash(T&& t) {
    return hasher< typename std::decay<T>::type >()(std::forward<T>(t));
  }
  inline namespace literals {
    std::size_t constexpr operator "" _hash(const char* s,size_t) {
      return hasher<std::string>()(s);
    }
  }
}
using namespace my_hash::literals;
void one() {} void two() {} void other() {}

void foo( const std::string& value )
{
  switch( my_hash::hash(value) )
  {
    case "one"_hash: one(); break;
    case "two"_hash: two(); break;
    /*many more cases*/
    default: other(); break;
  }
}

ejemplo en vivo

Tenga en cuenta la principal diferencia: std::hash no se puede utilizar, ya que no tenemos control sobre el algoritmo de std::hash , y debemos constexpr a constexpr como un constexpr para evaluarlo en tiempo de compilación. Además, no hay hashes "transparentes" en std , por lo que no puede (sin crear std::string ) hash un búfer de caracteres sin formato como std::string .

Puse el hasher personalizado de std::string (con soporte transparente const char* ) en un espacio de nombres my_hash , por lo que puedes almacenarlo en std::unordered_map si necesitas consistencia.

Basado en la excelente respuesta de @ JerryCoffin y el hilo de comentarios debajo, pero con un intento de escribirlo con las mejores prácticas actuales de C ++ 11 (¡en lugar de anticiparlas!).

Tenga en cuenta que usar un "hash puro" para un case declaración de switch es peligroso. Después, querrá hacer una == comparación para confirmar que funcionó.

Answer 5

Este fragmento está basado en el de Clement JACOB. Pero funciona con clang también. Y debería ser más rápido en la compilación (tiene solo una llamada recursiva, no dos como en la publicación original).

#include <iostream>
#include <string>
#include <vector>

static constexpr unsigned int crc_table[256] = {
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    0xe963a535, 0x9e6495a3,    0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};


template<int size, int idx = 0, class dummy = void>
struct MM{
  static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF)
  {
      return MM<size, idx+1>::crc32(str, (prev_crc >> 8) ^ crc_table[(prev_crc ^ str[idx]) & 0xFF] );
  }
};

// This is the stop-recursion function
template<int size, class dummy>
struct MM<size, size, dummy>{
  static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF)
  {
      return prev_crc^ 0xFFFFFFFF;
  }
};

// This don''t take into account the nul char
#define COMPILE_TIME_CRC32_STR(x) (MM<sizeof(x)-1>::crc32(x))


template<unsigned int crc>
void PrintCrc()
{
    std::cout << crc << std::endl;
}


int main()
{

    PrintCrc<COMPILE_TIME_CRC32_STR("HAH")>();
}

Ver prueba de concepto here

Answer 6

Esto es un poco tarde, pero logré implementar una función CRC32 en tiempo de compilación con el uso de constexpr . El problema es que, en el momento de redactar este informe, solo funciona con GCC y no con MSVC ni con el compilador de Intel.

Aquí está el fragmento de código:

// CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] = {
    0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
    0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
    0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
...
};
template<size_t idx>
constexpr uint32_t crc32(const char * str)
{
    return (crc32<idx-1>(str) >> 8) ^ crc_table[(crc32<idx-1>(str) ^ str[idx]) & 0x000000FF];
}

// This is the stop-recursion function
template<>
constexpr uint32_t crc32<size_t(-1)>(const char * str)
{
    return 0xFFFFFFFF;
}

// This doesn''t take into account the nul char
#define COMPILE_TIME_CRC32_STR(x) (crc32<sizeof(x) - 2>(x) ^ 0xFFFFFFFF)

enum TestEnum
{
    CrcVal01 = COMPILE_TIME_CRC32_STR("stack-overflow"),
};

CrcVal01 es igual a 0x335CC04A

¡Espero que esto te ayudará!

Answer 7

Lo siguiente funciona en GCC 4.6.1, y puede usar hash o pack en bloques de interruptores.

/* Fast simple string hash (Bernstein?) */                                       
constexpr unsigned int hash(const char *s, int off = 0) {                        
    return !s[off] ? 5381 : (hash(s, off+1)*33) ^ s[off];                           
}                                                                                

/* Pack the string into an unsigned int                                          
 * Using 7 bits (ascii) it packs 9 chars into a uint64_t                         
 */                                                                              
template <class T = uint64_t, unsigned int Bits = 7>                             
constexpr T pack(const char *s, unsigned int off = 0) {                          
    return (Bits*off >= CHAR_BIT*sizeof(T) || !s[off]) ? 0 :                     
        (((T)s[off] << (Bits*off)) | pack(s,off+1));                             
}  

GCC aparentemente (?) No permite llamadas recursivas donde pasamos s+1 con s un puntero, por lo que utilizo la variable off .

Answer 8

Otra solución basada en la de Clement JACOB, que usa C ++ 11 constexpr (no C ++ 14 extendido) pero que tiene solo una recursión.

namespace detail {
// CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... }

template<size_t idx>
constexpr uint32_t combine_crc32(const char * str, uint32_t part) {
  return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
}

template<size_t idx>
constexpr uint32_t crc32(const char * str) {
  return combine_crc32<idx>(str, crc32<idx - 1>(str));
}

// This is the stop-recursion function
template<>
constexpr uint32_t crc32<size_t(-1)>(const char * str) {
  return 0xFFFFFFFF;
}

} //namespace detail

template <size_t len>
constexpr uint32_t ctcrc32(const char (&str)[len]) {
  return detail::crc32<len - 2>(str) ^ 0xFFFFFFFF;
}

Alguna explicación

• Estamos utilizando una única recursión, por lo que la función funciona bien incluso para cadenas más largas.
• La función adicional combine_crc32 nos permite almacenar el resultado de una recursión bajo una part variable y usarla dos veces. Esta función es un paseo para la limitación de C ++ 11 que no permite las declaraciones de variables locales.
• La función ctcrc32 espera una cadena literal, que se pasa como un const char (&)[len] . De esta forma, podemos obtener la longitud de la cadena como un parámetro de plantilla y no tenemos que depender de macros.

Answer 9

Tenga en cuenta que el formulario que se muestra aquí no fue aceptado en el estándar, como se indica a continuación.

Se espera que el procesamiento de cadenas de tiempo de compilación sea posible a través de los literales definidos por el usuario propuestos en N2765 .
Como ya mencioné, no conozco ningún compilador que lo implemente actualmente y, sin el soporte del compilador, solo se puede adivinar el trabajo.

En §2.13.7.3 y 4 del draft tenemos lo siguiente:

De lo contrario (S contiene una plantilla de operador literal), L se trata como una llamada de la forma
operador "" X <''c1'', ''c2'', ..., ''ck''> () donde n es la secuencia de caracteres fuente c1c2 ... ck. [Nota: la secuencia c1c2 ... ck solo puede contener caracteres del conjunto de caracteres básicos de origen. -finalizar nota]

Combine eso con constexpr y deberíamos haber compilado el procesamiento de cadenas de tiempo.

actualización: pasé por alto que estaba leyendo el párrafo equivocado, este formulario está permitido para literales enteros definidos por el usuario y literales flotantes, pero aparentemente no para literales -string (§2.13.7.5).
Esta parte de la propuesta parece no haber sido aceptada.

Dicho esto, con mi visión limitada en C ++ 0x, podría verse algo como esto (lo más probable es que haya algo mal):

template<char c, char... str>
struct hash {
    static const unsigned result = c + hash<str...>::result;
};

template<char c>
struct hash {
    static const unsigned result = c;
};

template<char... str> 
constexpr unsigned
operator "" _hash() {
    return hash<str>::result;
}

// update: probably wrong, because the above 
// form is not allowed for string-literals:    
const unsigned h = "abcd"_hash;

Si el enfoque de Jerrys funciona, entonces lo siguiente debería funcionar:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}