Line data    Source code

       1           0 : /*
       2             :  * Copyright (c) 2022 Meta
       3             :  *
       4             :  * SPDX-License-Identifier: Apache-2.0
       5             :  */
       6             : 
       7             : #ifndef ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_
       8             : #define ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_
       9             : 
      10             : #include <stddef.h>
      11             : #include <stdint.h>
      12             : 
      13             : #include <zephyr/sys/__assert.h>
      14             : #include <zephyr/sys/util_macro.h>
      15             : 
      16             : #ifdef __cplusplus
      17             : extern "C" {
      18             : #endif
      19             : 
      20             : /**
      21             :  * @ingroup hashmap_apis
      22             :  * @defgroup hash_functions Hash Functions
      23             :  * @{
      24             :  */
      25             : 
      26             : /**
      27             :  * @brief 32-bit Hash function interface
      28             :  *
      29             :  * Hash functions are used to map data from an arbitrarily large space to a
      30             :  * (typically smaller) fixed-size space. For a given input, a hash function will
      31             :  * consistently generate the same, semi-unique numerical value. Even for
      32             :  * marginally different data, a good hash function will distribute the entropy
      33             :  * almost evenly over all bits in the hashed value when combined with modulo
      34             :  * arithmetic over a finite-sized numeric field.
      35             :  *
      36             :  * @param str a string of input data
      37             :  * @param n the number of bytes in @p str
      38             :  *
      39             :  * @return the numeric hash associated with @p str
      40             :  */
      41           1 : typedef uint32_t (*sys_hash_func32_t)(const void *str, size_t n);
      42             : 
      43             : /**
      44             :  * @brief The naive identity hash function
      45             :  *
      46             :  * This hash function requires that @p n is equal to the size of a primitive
      47             :  * type, such as `[u]int8_t`, `[u]int16_t`, `[u]int32_t`, `[u]int64_t`,
      48             :  * `float`, `double`, or `void *`, and that the alignment of @p str agrees
      49             :  * with that of the respective native type.
      50             :  *
      51             :  * @note The identity hash function is used for testing @ref sys_hashmap.
      52             :  *
      53             :  * @param str a string of input data
      54             :  * @param n the number of bytes in @p str
      55             :  *
      56             :  * @return the numeric hash associated with @p str
      57             :  */
      58           1 : static inline uint32_t sys_hash32_identity(const void *str, size_t n)
      59             : {
      60             :         switch (n) {
      61             :         case sizeof(uint8_t):
      62             :                 return *(uint8_t *)str;
      63             :         case sizeof(uint16_t):
      64             :                 return *(uint16_t *)str;
      65             :         case sizeof(uint32_t):
      66             :                 return *(uint32_t *)str;
      67             :         case sizeof(uint64_t):
      68             :                 return (uint32_t)(*(uint64_t *)str);
      69             :         default:
      70             :                 break;
      71             :         }
      72             : 
      73             :         __ASSERT(false, "invalid str length %zu", n);
      74             : 
      75             :         return 0;
      76             : }
      77             : 
      78             : /**
      79             :  * @brief Daniel J.\ Bernstein's hash function
      80             :  *
      81             :  * Some notes:
      82             :  * - normally, this hash function is used on NUL-terminated strings
      83             :  * - it has been modified to support arbitrary sequences of bytes
      84             :  * - it has been modified to use XOR rather than addition
      85             :  *
      86             :  * @param str a string of input data
      87             :  * @param n the number of bytes in @p str
      88             :  *
      89             :  * @return the numeric hash associated with @p str
      90             :  *
      91             :  * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_DJB2}
      92             :  *
      93             :  * @see https://theartincode.stanis.me/008-djb2/
      94             :  */
      95           1 : uint32_t sys_hash32_djb2(const void *str, size_t n);
      96             : 
      97             : /**
      98             :  * @brief Murmur3 hash function
      99             :  *
     100             :  * @param str a string of input data
     101             :  * @param n the number of bytes in @p str
     102             :  *
     103             :  * @return the numeric hash associated with @p str
     104             :  *
     105             :  * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_MURMUR3}
     106             :  *
     107             :  * @see https://en.wikipedia.org/wiki/MurmurHash
     108             :  */
     109           1 : uint32_t sys_hash32_murmur3(const void *str, size_t n);
     110             : 
     111             : /**
     112             :  * @brief System default 32-bit hash function
     113             :  *
     114             :  * @param str a string of input data
     115             :  * @param n the number of bytes in @p str
     116             :  *
     117             :  * @return the numeric hash associated with @p str
     118             :  */
     119           1 : static inline uint32_t sys_hash32(const void *str, size_t n)
     120             : {
     121             :         if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_IDENTITY)) {
     122             :                 return sys_hash32_identity(str, n);
     123             :         }
     124             : 
     125             :         if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_DJB2)) {
     126             :                 return sys_hash32_djb2(str, n);
     127             :         }
     128             : 
     129             :         if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_MURMUR3)) {
     130             :                 return sys_hash32_murmur3(str, n);
     131             :         }
     132             : 
     133             :         __ASSERT(0, "No default 32-bit hash. See CONFIG_SYS_HASH_FUNC32_CHOICE");
     134             : 
     135             :         return 0;
     136             : }
     137             : 
     138             : /**
     139             :  * @}
     140             :  */
     141             : 
     142             : #ifdef __cplusplus
     143             : }
     144             : #endif
     145             : 
     146             : #endif /* ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_ */