Local Database

Organiza tus páginas con colecciones Guarda y categoriza el contenido según tus preferencias.

Decodifica hash y prefijos hash

Todas las listas se entregan con una codificación especial para reducir el tamaño. Esta codificación funciona reconociendo que las listas de Navegación segura de Google contienen, de manera conceptual, un conjunto de hashes o prefijos de hash, que son indistinguibles de los números enteros aleatorios. Si ordenáramos estos números enteros y tomáramos su diferencia adyacente, se espera que esa diferencia adyacente sea “pequeña” en cierto sentido. Luego, la codificación Golomb-Rice aprovecha esta pequeñez.

Supongamos que se deben transmitir tres expresiones de prefijo de ruta de sufijo de host, a saber, a.example.com/, b.example.com/ y y.example.com/, con prefijos de hash de 4 bytes. Supongamos además que el parámetro de Rice, denotado por k, se elige como

1. El servidor comenzaría por calcular el hash completo de estas cadenas, que son, respectivamente:

291bc5421f1cd54d99afcc55d166e2b9fe42447025895bf09dd41b2110a687dc  a.example.com/
1d32c5084a360e58f1b87109637a6810acad97a861a7769e8f1841410d2a960c  b.example.com/
f7a502e56e8b01c6dc242b35122683c9d25d07fb1f532d9853eb0ef3ff334f03  y.example.com/

Luego, el servidor forma prefijos de hash de 4 bytes para cada uno de los elementos anteriores, que son los primeros 4 bytes del hash completo de 32 bytes, interpretados como números enteros de 32 bits de big-endian. El orden de bytes big endian se refiere al hecho de que el primer byte del hash completo se convierte en el byte más significativo del número entero de 32 bits. Este paso genera los números enteros 0x291bc542, 0x1d32c508 y 0xf7a502e5.

Es necesario que el servidor ordene estos tres prefijos de hash de forma léxica (equivalente a la ordenación numérica en formato big endian), y el resultado de la ordenación es 0x1d32c508, 0x291bc542, 0xf7a502e5. El primer prefijo de hash se almacena sin cambios en el campo first_value.

Luego, el servidor calcula las dos diferencias adyacentes, que son 0xbe9003a y 0xce893da3, respectivamente. Dado que se elige que k sea 30, el servidor divide estos dos números en las partes del cociente y del resto que tienen 2 y 30 bits de longitud, respectivamente. Para el primer número, la parte del cociente es cero y el resto es 0xbe9003a. Para el segundo número, la parte del cociente es 3 porque los dos bits más significativos son 11 en formato binario y el resto es 0xe893da3. Para un cociente q determinado, se codifica en (1 << q) - 1 con exactamente 1 + q bits; el resto se codifica directamente con k bits. La parte del cociente del primer número se codifica como 0 y la parte del resto está en formato binario 001011111010010000000000111010. La parte del cociente del segundo número se codifica como 0111 y la parte del resto es 001110100010010011110110100011.

Cuando estos números se forman en una cadena de bytes, se usa el formato little endian. Conceptualmente, puede ser más fácil imaginar una cadena de bits larga que se forma a partir de los bits menos significativos: tomamos la parte del cociente del primer número y le agregamos la parte del resto del primer número. Luego, agregamos la parte del cociente del segundo número y la parte del resto. Esto debería generar el siguiente número grande (se agregaron saltos de línea y comentarios para mayor claridad):

001110100010010011110110100011 # Second number, remainder part
0111 # Second number, quotient part
001011111010010000000000111010 # First number, remainder part
0 # First number, quotient part

Si se escribe en una sola línea, sería lo siguiente:

00111010001001001111011010001101110010111110100100000000001110100

Obviamente, esta cantidad supera con creces los 8 bits disponibles en un solo byte. Luego, la codificación little endian toma los 8 bits menos significativos de ese número y los muestra como el primer byte, que es 01110100. Para mayor claridad, podemos agrupar la cadena de bits anterior en grupos de ocho, comenzando por los bits menos significativos:

0 01110100 01001001 11101101 00011011 10010111 11010010 00000000 01110100

Luego, la codificación little endian toma cada byte de la derecha y lo coloca en una cadena de bytes:

01110100
00000000
11010010
10010111
00011011
11101101
01001001
01110100
00000000

Se puede ver que, dado que conceptualmente anteponemos partes nuevas al número grande de la izquierda (es decir, agregamos más bits significativos), pero codificamos desde la derecha (es decir, los bits menos significativos), la codificación y decodificación se pueden realizar de forma incremental.

Esto genera lo siguiente:

additions_four_bytes {
  first_value: 489866504
  rice_parameter: 30
  entries_count: 2
  encoded_data: "t\000\322\227\033\355It\000"
}

El cliente simplemente sigue los pasos anteriores a la inversa para decodificar los prefijos de hash.

Decodifica los índices de eliminación

Los índices de eliminación se codifican con la misma técnica que se mencionó anteriormente, con números enteros de 32 bits.