php - tag - Función perfecta de hash para códigos de orden de lectura humana

get tag name wordpress

Question

Estoy intentando generar códigos de orden legibles por humanos no secuenciales derivados de (digamos) una identificación interna de 32 bits sin signo que comienza en 1 y se incrementa automáticamente para cada pedido nuevo.

En mi código de ejemplo a continuación, ¿cada $hash será único? (Planeo basar34 codificar $hash para que sea legible por humanos.)

<?php
function int_hash($key) {
  $key = ($key^0x47cb8a8c) ^ ($key<<12);
  $key = ($key^0x61a988bc) ^ ($key>>19);
  $key = ($key^0x78d2a3c8) ^ ($key<<5);
  $key = ($key^0x5972b1be) ^ ($key<<9);
  $key = ($key^0x2ea72dfe) ^ ($key<<3);
  $key = ($key^0x5ff1057d) ^ ($key>>16);
  return $key;
}

for($order_id = 1; $order_id <= PHP_INT_MAX; ++$order_id) {
  $hash = int_hash($order_id);
}
?>

Si no, ¿hay alguna sugerencia sobre cómo reemplazar int_hash ?

El resultado de decir, base34 codificando un md5($order_id) es demasiado largo para mi gusto.

Answer 1

En mi código de ejemplo a continuación, ¿cada $hash será único?

Casi. (Lo cual, supongo, significa "no, pero de una manera que se soluciona fácilmente".) Su función consiste en una secuencia de pasos independientes; la función general es bijective (reversible) si y solo si cada uno de esos pasos es. (¿Ves por qué?)

Ahora, cada paso tiene una de las siguientes formas:

  $key = ($key ^ CONSTANT) ^ ($key >> NUM_BITS);
  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

con NUM_BITS != 0 .

En realidad, podemos tratar estos como variantes de una sola forma, viendo la primera como casi equivalente a esto:

  $key = invert_order_of_bits($key); # clearly bijective
  $constant = invert_order_of_bits(CONSTANT);
  $key = ($key ^ $constant) ^ ($key << NUM_BITS);
  $key = invert_order_of_bits($key); # clearly bijective

Entonces, todo lo que necesitamos es mostrar que esto:

  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

es biyectiva Ahora, XOR es conmutativo y asociativo, por lo que lo anterior es equivalente a esto:

  $key = $key ^ ($key << NUM_BITS);
  $key = $key ^ CONSTANT;

y (x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x , entonces claramente XOR-ing con un valor constante es reversible (re-XOR-ing con el mismo valor); entonces todo lo que tenemos que mostrar es que esto es biyectivo:

  $key = $key ^ ($key << NUM_BITS);

cada vez que NUM_BITS != 0 .

Ahora, no estoy escribiendo una prueba rigurosa, así que solo daré un ejemplo razonado de cómo revertir esto. Supongamos que $key ^ ($key << 9) es

0010 1010 1101 1110 0010 0101 0000 1100

¿Cómo obtenemos $key ? Bueno, sabemos que los últimos nueve bits de $key << 9 son todos ceros, por lo que sabemos que los últimos nueve bits de $key ^ ($key << 9) son los mismos que los últimos nueve bits de $key . Así que $key ve como

bbbb bbbb bbbb bbbb bbbb bbb1 0000 1100

así que $key << 9 parece

bbbb bbbb bbbb bb10 0001 1000 0000 0000

así que $key ve como

bbbb bbbb bbbb bb00 0011 1101 0000 1100

(por XOR-ing $key ^ ($key << 9) con $key << 9 ), así que $key << 9 parece

bbbb b000 0111 1010 0001 1000 0000 0000

así que $key ve como

bbbb b010 1010 0100 0011 1101 0000 1100

así que $key << 9 parece

0101 1000 0111 1010 0001 1000 0000 0000

así que $key ve como

0111 0010 1010 0100 0011 1101 0000 1100

Asi que . . . ¿Por qué digo "casi" en lugar de "sí"? ¿Por qué su función hash no es perfectamente biyectiva? Es porque en PHP, los operadores de desplazamiento bit a bit >> y << no son del todo simétricos, y mientras $key = $key ^ ($key << NUM_BITS) es completamente reversible, $key = $key ^ ($key >> NUM_BITS) no es. (Arriba, cuando escribí que los dos tipos de pasos eran " casi equivalentes", realmente quise decir "casi". ¡Hace una diferencia!) Mire, mientras que << trata el bit de signo como cualquier otro bit, y cambia fuera de existencia (trayendo un bit cero a la derecha), >> trata el bit de signo especialmente, y lo "extiende": el bit que trae a la izquierda es igual al bit de signo. (NB Su pregunta menciona valores "sin signo de 32 bits", pero PHP en realidad no admite eso, sus operaciones bit a bit siempre están en enteros con signo .)

Debido a esta extensión de signo, si $key comienza con 0 , entonces $key >> NUM_BITS comienza con 0 , y si $key comienza con 1 , entonces $key >> NUM_BITS también comienza con 1 . En cualquier caso, $key ^ ($key >> NUM_BITS) comenzará con un 0 . Has perdido exactamente un poco de entropía. Si me das $key ^ ($key >> 9) , y no me dices si $key es negativo, lo mejor que puedo hacer es calcular dos valores posibles para $key : uno negativo, uno positivo o cero.

Realiza dos pasos que usan desplazamiento a la derecha en lugar de a la izquierda, así que pierde dos bits de entropía. (Estoy agitando ligeramente la mano, todo lo que he demostrado es que pierdes al menos un bit y como mucho dos bits), pero confío en que, debido a la naturaleza de los pasos entre esos pasos del cambio a la derecha, de hecho, pierdes dos bits completos). Para cualquier valor de salida dado, hay exactamente cuatro valores de entrada distintos que podrían producirlo. Entonces no es único, pero es casi único; y se puede arreglar fácilmente, ya sea por:

• cambiando los dos pasos de desplazamiento a la derecha para usar los cambios a la izquierda; o
• moviendo ambos pasos del cambio hacia la derecha al comienzo de la función, antes de cualquier paso hacia la izquierda, y diciendo que las salidas son únicas para entradas entre 0 y 2 ³¹ -1 en lugar de entradas entre 0 y 2 ³² -1.