如何在 C 中散列 CPU ID

Question

我正在尝试缩短我的微控制器 (STM32F1) 的 cpu id。

cpu id 由 3 个字（3 x 4 字节）组成。这是由 3 个单词构建的 id 字符串：980416578761680031125348904

我找到了一个非常有用的库来执行此操作。

库是Hashids，有C代码

我尝试在 PC 上使用 "Code Blocks IDE" 构建测试代码并且代码有效。

但是当我将代码移动到嵌入式端（Keil v5 IDE）时，我在 strdup() 函数上遇到错误："strdup implicit declaration of function".

问题与 strdup 函数有关，它不是标准库函数，没有包含在 string.h 中。

我会避免用自定义函数（模仿 strdup 的行为）替换 strdup 函数以避免内存泄漏，因为 strdup 使用 malloc 复制字符串。

是否有不同的方法来压缩长数字？

感谢您的帮助！

<---附录--->

这是使用 strdup 的函数。

    /* common init */
    struct hashids_t *
    hashids_init3(const char *salt, size_t min_hash_length, const char *alphabet)
    {
    struct hashids_t *result;
    unsigned int i, j;
    size_t len;
    char ch, *p;

    hashids_errno = HASHIDS_ERROR_OK;

    /* allocate the structure */
    result = _hashids_alloc(sizeof(struct hashids_t));
    if (HASHIDS_UNLIKELY(!result)) {
        hashids_errno = HASHIDS_ERROR_ALLOC;
        return NULL;
    }

    /* allocate enough space for the alphabet and its copies */
    len = strlen(alphabet) + 1;
    result->alphabet = _hashids_alloc(len);
    result->alphabet_copy_1 = _hashids_alloc(len);
    result->alphabet_copy_2 = _hashids_alloc(len);
    if (HASHIDS_UNLIKELY(!result->alphabet || !result->alphabet_copy_1
        || !result->alphabet_copy_2)) {
        hashids_free(result);
        hashids_errno = HASHIDS_ERROR_ALLOC;
        return NULL;
    }

    /* extract only the unique characters */
    result->alphabet[0] = '[=11=]';
    for (i = 0, j = 0; i < len; ++i) {
        ch = alphabet[i];
        if (!strchr(result->alphabet, ch)) {
            result->alphabet[j++] = ch;
        }
    }
    result->alphabet[j] = '[=11=]';

    /* store alphabet length */
    result->alphabet_length = j;

    /* check length and whitespace */
    if (result->alphabet_length < HASHIDS_MIN_ALPHABET_LENGTH) {
        hashids_free(result);
        hashids_errno = HASHIDS_ERROR_ALPHABET_LENGTH;
        return NULL;
    }
    if (strchr(result->alphabet, ' ')) {
        hashids_free(result);
        hashids_errno = HASHIDS_ERROR_ALPHABET_SPACE;
        return NULL;
    }

    /* copy salt */
    result->salt = strdup(salt ? salt : HASHIDS_DEFAULT_SALT);
    result->salt_length = (unsigned int) strlen(result->salt);

    /* allocate enough space for separators */
    result->separators = _hashids_alloc((size_t)
        (ceil((float)result->alphabet_length / HASHIDS_SEPARATOR_DIVISOR) + 1));
    if (HASHIDS_UNLIKELY(!result->separators)) {
        hashids_free(result);
        hashids_errno = HASHIDS_ERROR_ALLOC;
        return NULL;
    }

    /* non-alphabet characters cannot be separators */
    for (i = 0, j = 0; i < strlen(HASHIDS_DEFAULT_SEPARATORS); ++i) {
        ch = HASHIDS_DEFAULT_SEPARATORS[i];
        if ((p = strchr(result->alphabet, ch))) {
            result->separators[j++] = ch;

            /* also remove separators from alphabet */
            memmove(p, p + 1,
                strlen(result->alphabet) - (p - result->alphabet));
        }
    }

    /* store separators length */
    result->separators_count = j;

    /* subtract separators count from alphabet length */
    result->alphabet_length -= result->separators_count;

    /* shuffle the separators */
    hashids_shuffle(result->separators, result->separators_count,
        result->salt, result->salt_length);

    /* check if we have any/enough separators */
    if (!result->separators_count
        || (((float)result->alphabet_length / (float)result->separators_count)
                > HASHIDS_SEPARATOR_DIVISOR)) {
        unsigned int separators_count = (unsigned int)ceil(
            (float)result->alphabet_length / HASHIDS_SEPARATOR_DIVISOR);

        if (separators_count == 1) {
            separators_count = 2;
        }

        if (separators_count > result->separators_count) {
            /* we need more separators - get some from alphabet */
            int diff = separators_count - result->separators_count;
            strncat(result->separators, result->alphabet, diff);
            memmove(result->alphabet, result->alphabet + diff,
                result->alphabet_length - diff + 1);

            result->separators_count += diff;
            result->alphabet_length -= diff;
        } else {
            /* we have more than enough - truncate */
            result->separators[separators_count] = '[=11=]';
            result->separators_count = separators_count;
        }
    }

    /* shuffle alphabet */
    hashids_shuffle(result->alphabet, result->alphabet_length,
        result->salt, result->salt_length);

    /* allocate guards */
    result->guards_count = (unsigned int) ceil((float)result->alphabet_length
                                               / HASHIDS_GUARD_DIVISOR);
    result->guards = _hashids_alloc(result->guards_count + 1);
    if (HASHIDS_UNLIKELY(!result->guards)) {
        hashids_free(result);
        hashids_errno = HASHIDS_ERROR_ALLOC;
        return NULL;
    }

    if (HASHIDS_UNLIKELY(result->alphabet_length < 3)) {
        /* take some from separators */
        strncpy(result->guards, result->separators, result->guards_count);
        memmove(result->separators, result->separators + result->guards_count,
            result->separators_count - result->guards_count + 1);

        result->separators_count -= result->guards_count;
    } else {
        /* take them from alphabet */
        strncpy(result->guards, result->alphabet, result->guards_count);
        memmove(result->alphabet, result->alphabet + result->guards_count,
            result->alphabet_length - result->guards_count + 1);

        result->alphabet_length -= result->guards_count;
    }

    /* set min hash length */
    result->min_hash_length = min_hash_length;

    /* return result happily */
    return result;
}

Answer 1

您可以像这样轻松实现 strdup 自己：

char* strdup (const char* str)
{
  size_t size = strlen(str);
  char* result = malloc(size);  
  if(result != NULL)
  {
    memcpy(result, str, size+1);
  }
  return result;
}

也就是说，在嵌入式系统上使用 malloc 或 strdup 很可能只是胡说八道，see this。您也不会使用浮点数。总体而言，该库似乎是由具有桌面意识的人编写的。

如果您要在嵌入式系统上实现诸如链式哈希 table 之类的东西，您将使用静态分配的内存池，而不是 malloc。出于这个原因，我可能会选择非链接的（重复时，选择缓冲区中的下一个空闲位置）。

Answer 2

唯一设备 ID 寄存器（96 位）位于地址 0x1FFFF7E8 下。它是工厂编程的并且是只读的。您可以直接阅读它，而无需使用任何其他外部库。例如：

unsigned int b = *(0x1FFFF7E8);

应该为您提供唯一设备 ID 的前 32 位 (31:0)。如果你想像提到的库一样检索字符串，以下应该有效：

sprintf(id, "%08X%08X%08X", *(0x1FFFF7E8), *(0x1FFFF7E8 + 4), *(0x1FFFF7E8 + 8);

可能需要进行一些额外的转换，但通常这就是库所做的。有关更多详细信息，请参阅 STM32F1xx 参考手册 (RM0008) 第 30.2 节。对于 MCU 的 Cortex-M4 系列，要读取的确切内存位置不同。

Answer 3

真正的问题似乎是

Is there a different approach to compress long numbers?

有很多。它们在几个方面有所不同，包括输入的哪些位对输出有贡献，有多少输入映射到同一输出，以及输入的何种转换方式使输出保持不变。

作为一个简单的例子，您可以通过以下任何一种方法将输入压缩为一位：

选择输入的最低位
选择输入的最高位
输出总是1
等等

或者你可以使用输入中 1 的位数作为输出来压缩到 7 位。

None 当然，您可能会对这些特定选项感兴趣。

也许您对为 96 位输入生成 32 位输出更感兴趣。 请注意，在这种情况下，平均至少有 2⁶⁴ 个可能的输入映射到每个可能的输出。 这仅取决于输入和输出的大小，与转换的任何细节无关。

例如，假设您有

uint32_t *cpuid = ...;

指向硬件CPU ID。您可以从中生成一个 32 位值，该值取决于输入的所有位，只需执行以下操作：

uint32_t cpuid32 = cpuid[0] ^ cpuid[1] ^ cpuid[2];

这是否适合您的目的取决于您打算如何使用它。

如何在 C 中散列 CPU ID

How to Hash CPU ID in C

c

compression

embedded

hash

hashids