Algoritmo para obtener el CRC usando una tabla

En los temas anteriores hemos aplicado mejoras empezando por el algoritmo de la división para obtener el resto, pasando al algoritmo del resto pues no nos interesaba el cociente de la división, mejorándolo con otro para evitar el aumento de la entrada y por último llegábamos al algoritmo con índice de un byte, donde pasábamos al tercer argumento de la función mod(x, y, z) un índice que era un valor binario entre 256 posibles. Esta mejora que veremos en este tema nos permitirá almacenar en una tabla esos 256 valores para no tener que estar calculándolos con cada byte del archivo.

Habíamos terminado el tema anterior con la recurrencia siguiente, donde x[i, d] es el byte tomado en la iteración i-ésima, con una longitud de d bits. Y que ρ es el resto r'i-1 de la iteración anterior. Con r' indicamos que es el CRC de la entrada aumentada, aunque se obtiene sobre la entrada sin aumentar x, no sobre x':

r'i = mod( 0d , y , ( x[i, d] + ρ[0, d] ) 10w-d ) + ρ[d, w-d] 10d

Como x[i, d] + ρ[0, d] ocupa 8 bits, este término sólo tendrá 28 = 256 valores posibles. Así que tendremos 256 índices entre 0·10w-d y 11111111·10w-d, lo que nos permitirá almacenarlos en un tabla y no tener que estar ejecutando mod(0, poly, index) con cada byte del bucle, algo que haremos en este apartado.

Vease que no es necesario multiplicar x[i, d] + ρ[0, d] por 10w-d para componer el índice de la tabla, puesto que este agregado de w-d ceros lo tendremos en cuenta cuando generemos la tabla con los 256 resultados posibles de la expresión (x[i, d] + ρ[0, d]) 10w-d.

Así que nuestra recurrencia queda como sigue:

r'i = table[x[i, d] + ρ[0, d]] + ρ[d, w-d] 10d

Veamos como generamos la tabla.Supongamos que index = 01111010, 0x7A en hexadecimal, 122 en decimal, letra "z" en ASCII. Y que el polinomio es 0x9B con un ancho w = 8 bits (CRC-8/LTE). Agregando el 1 inicial es poly = (1)10011011. En la herramienta Web Tools online podemos obtener mod(08, poly, index) = mod(08, 110011011, 01111010) = 00101010 con la siguiente traza:

00000000 MOD 110011011 ⇒ 
     001111010    00000000
k=0  011110100    0000000
k=1  111101000    000000
     111101000 XOR 110011011 = 001110011
k=2  011100110    00000
k=3  111001100    0000
     111001100 XOR 110011011 = 001010111
k=4  010101110    000
k=5  101011100    00
     101011100 XOR 110011011 = 011000111
k=6  110001110    0
     110001110 XOR 110011011 = 000010101
k=7  000101010 

Podemos observar que el primer 1 del polinomio no afecta al resultado final, pues el primer dígito del resto siempre será cero, resaltado en azul. El resto tiene w= 8 dígitos y se resalta en amarillo. Así que podríamos ahorrarnos este primer 1 en poly = (1)10011011 y el polinomio pasaría a ser poly = 10011011 si hiciéramos una ligera modificación en el cálculo anterior de la siguiente forma:

Poly 10011011
Trace for index=0b01111010, 0x7A, 122 : 
j=0 ⇒ 01111010 << 1 = 11110100        = 11110100 ⇒ 0xF4
j=1 ⇒ 11110100 << 1 = 11101000 ^ Poly = 01110011 ⇒ 0x73
j=2 ⇒ 01110011 << 1 = 11100110        = 11100110 ⇒ 0xE6
j=3 ⇒ 11100110 << 1 = 11001100 ^ Poly = 01010111 ⇒ 0x57
j=4 ⇒ 01010111 << 1 = 10101110        = 10101110 ⇒ 0xAE
j=5 ⇒ 10101110 << 1 = 01011100 ^ Poly = 11000111 ⇒ 0xC7
j=6 ⇒ 11000111 << 1 = 10001110 ^ Poly = 00010101 ⇒ 0x15
j=7 ⇒ 00010101 << 1 = 00101010        = 00101010 ⇒ 0x2A

Como el dividendo, es decir 08 en mod(08, 110011011, 01111010), son siempre 8 ceros, sólo es necesario tener en cuenta el tercer argumento, es decir, el índice 01111010. Iteramos de 0 a 7 desplazando un bit a la izquierda, lo que equivale a eliminar el primer bit por la izquierda y agregar un cero por la derecha. Si el primer bit es un uno entonces sumamos XOR (^) con el poly (sin el (1) inicial) .

Se trata entonces de iterar por los 256 valores posibles del índice, entre 0b00000000 y 0b11111111, 0 y 255 en decimal, e ir obteniendo el resto de cada índice. Cada uno de estos índices se multiplica por 10w-d. En el ejemplo como w = 8 y d = 8 entonces 10w-d = 1 y no produce ningún efecto. Si fuera un polinomio con ancho w = 24 bits multiplicaríamos por 1016 lo que equivale a agregar 16 ceros al índice antes de iniciar el bucle de generación. Ambos procedimientos son totalmente equivalentes, hacen lo mismo.

El código para generar la tabla es el siguiente:

let widthBits = Math.max(width, 8);
poly = hexToBin(poly).padStart(width, "0").padEnd(widthBits, "0");
let table = [];
for (let i=0; i<256; i++){
    let n = i.toString(2).padStart(8, "0") + "0".repeat(widthBits-8);
    for (let j=0; j<8; j++){
        let shifted = shiftLeft(n, 1);
        if (n[0] === "1") {
            n = xor(shifted, poly).padStart(widthBits, "0");
        } else {
            n = shifted;
        }
    }
    table.push(n);
}

Observe que no agregamos el (1) inicial al polinomio. Como en ejemplos anteriores, primero ajustamos al inicio al ancho w del polinomio (width en el código) y luego realizamos el ajuste al final para el caso de los polinomios con ancho inferior a 8. Esto ya fue explicado en el tema anterior.

Iteramos entre 0 y 255, pasando cada uno de estos números a binario con let n = i.toString(2). Ajustamos ceros a la izquierda para que tenga 8 bits. Y luego concatenamos por la derecha con "0".repeat(widthBits-8) para ejecutar la multiplicación del índice por 10w-d. Si w = d = 8 no tiene ningún efecto. Si fuera mayor, como w = 24, entonces multiplicamos por 1024-8 = 1016, lo que equivale a agregar widthBits-8 ceros a la derecha.

Desplazamos a la izquierda un bit y comprobamos si el primer bit es un uno, en cuyo caso sumamos XOR con el polinomio (sin el (1) inicial). Completamos con ceros por la izquierda pues la operación XOR elimina los ceros iniciales. Guardamos el resultado en la posición index de la tabla con table.push(n).

Repetimos nuevamente la recurrencia junto al esquema para comentar más detalles:

r'i = table[x[i, d] + ρ[0, d]] + ρ[d, w-d] 10d

Figura
Figura. Esquema algoritmo CRC de 24 bits con tabla

En el esquema de la Figura se presenta un CRC de 24 bits, 3 bytes. En input está la entrada sin aumentar de los bytes del archivo. El registro CRC se modifica en cada iteración de los bytes del archivo, resultando el CRC final cuando finalice el bucle.

Podemos identificar el top byte del CRC del paso anterior (byte 2) con ρ[0, d]. El byte de la entrada (input) es x[i, d]. La suma XOR entre ambos produce un índice (index) entre 0 y 255. Ese índice nos dará un valor en table[index].

Desplazamos el CRC del paso anterior 8 bits a la izquierda, que es el resultado de calcular ρ[d, w-d] 10d. Sumamos XOR con el valor de la tabla. El resultado será el nuevo CRC para el paso siguiente del bucle.

El código siguiente expone la función crcTableStringBasic() que implementa lo que hemos visto. No olvide que seguimos usando binarios representados en strings. En un siguiente apartado convertiremos este algoritmo en uno final con números binarios.

function crcTableStringBasic({arrayBytes=[], width=0, poly="0"}){
    let widthBits = Math.max(width, 8);
    poly = hexToBin(poly).padStart(width, "0").padEnd(widthBits, "0");
    let table = [];
    for (let i=0; i<256; i++){
        let n = i.toString(2).padStart(8, "0") + "0".repeat(widthBits-8);
        for (let j=0; j<8; j++){
            let shifted = shiftLeft(n, 1);
            if (n[0] === "1") {
                n = xor(shifted, poly).padStart(widthBits, "0");
            } else {
                n = shifted;
            }
        }
        table.push(n);
    }
    let crc = "0".repeat(widthBits);
    for (let i=0; i<arrayBytes.length; i++){
        let Byte = arrayBytes[i].toString(2).padStart(8, "0");
        let crcTopByte = shiftRight(crc, widthBits-8);
        let index = xor(crcTopByte, Byte);
        let tab = table[Number(`0b${index}`)];
        let crcShift = shiftLeft(crc, 8);
        crc = xor(crcShift, tab).padStart(widthBits, "0");
    }
    crc = crc.substr(0, width);
    return crc;
}

En el código anterior widthBits es el ancho w en bits del polinomio, sin incluir el (1) inicial. Ajustamos a 8 bits para el caso de polinomios con ancho inferior. Como el argumento poly es un hexadecimal representado en un string, usamos la función hexToBin(poly) que expusimos en un tema anterior para convertir a binario en string. No incluimos el (1) inicial. Rellenamos ceros por la izquierda para completar el tamaño w y, si el polinomio es tal que w<8, agregamos 8-w ceros por la derecha, lo que equivale a rellenar con padEnd(widthBits, "0"). Vease que si w≥8 entonces width es igual que widthBits y no produce ningún efecto el relleno por la derecha.

El siguiente paso es generar la tabla en un bucle que itera entre i=0 y i=255. En cada iteración convertimos i en un binario en string, completando con ceros a la izquierda 8 bits. Y agregando w-8 (widthBits-8) ceros a la derecha. Con esto multiplicamos por 10w-d el índice, pues en la recurrencia teníamos table[index] = (x[i, d] + ρ[0, d]) 10w-d.

Iteramos por los bits del índice n desde j=0 hasta j=7. Desplazamos un bit a la izquierda con shiftLeft(n, 1). Cuando el primer bit de la izquierda sea 1 sumaremos XOR con el polinomio. Al final de este bucle guardaremos el valor en la tabla.

A continuación se ejecuta el bucle que itera por los bytes de la entrada arrayBytes. Estos bytes nos vienen como números y los convertimos a binarios en string. Veamos una traza del CRC-24/LTE-A, polinomio de ancho w=24 bits, usando la entrada "123456789", presentando sólo la iteración del tercer byte (i=2):

i=2 ⇒ byte = arrayBytes[2] = 00110011
crcTopByte = crc >>> 16  = 101101111000110010010001 >>> 16 = 000000000000000010110111
index = byte ^ crcTopByte = 00110011 ^ 000000000000000010110111 = 10000100 (132)
tab = table[index] = 101000001010000101000101 ⇒ 0xA0A145
crcShift = crc << 8 = 101101111000110010010001 << 8 = 100011001001000100000000
crc = crcShift ^ table[index] = 100011001001000100000000 ^ 1011000011000001000101 =
      1011000011000001000101 ⇒ 0x2C3045

En esta traza los desplazamientos derecha e izquierda se ejecutan con las funciones shiftRight() y shiftLeft() sobre binarios en strings, aunque en la traza aparezcan escritas con >>> y << respectivamente.

Obtenemos el crcTopByte desplazando a la derecha w-8 (widthBits-8) bits, que para este ejemplo es 32-8=16 bits. Observe en la traza que se obtienen los 8 primeros bits resaltados en amarillo. Calculamos el índice sumando XOR este crcTopByte con el byte de la entrada. Vamos a la tabla a recuperar el valor almacenado en este índice con table[Number(`0b${index}`)], no olvidando que index es un binario en string y que lo tenemos que convertir a número para obtener la posición en ese array. Con esto tenemos ya en la variable tab el término table[x[i, d] + ρ[0, d]] de nuestra recurrencia. Para obtener ρ[d, w-d] 10d desplazamos a la izquierda d=8, pues es como multiplicar por 10d. Finalizamos sumando XOR ambos términos.

Detalles de implementación con números binarios en JavaScript

Antes de pasar a implementar con números el algoritmo anterior, conviene repasar como JavaScript maneja las operaciones binarias a nivel de bit (bitwise operators). Estas son AND (&), OR (|), XOR (^), NOT (~) y los operadores de desplazamiento izquierda (<<) y derecha (>> y >>>). No deben confundirse los operadores binarios & y | con los operadores lógicos && o ||.

El máximo entero que podemos representar en JavaScript es 0x1FFFFFFFFFFFFF con valor decimal 9007199254740991, que tiene 53 bits 1. Sin embargo para las operaciones binarias a nivel de bit JavaScript usa un registro con solo 32 bits, conformando enteros positivos y negativos entre los máximos valores decimales -2147483648 y +2147483647.

Si ejecutamos una operación como 187 & 220 donde los operandos son números decimales, JavaScript convierte esos operandos en enteros de 32 bits y luego realiza la operación alineando los bits por la derecha y aplicando la operación AND (&) bit a bit:

187 =             00000000000000000000000010111011
220 =             00000000000000000000000011011100
187 & 220 = 152 = 00000000000000000000000010011000

La operación anterior puede ejecutarse con 0b10111011 & 0b11011100 usando binarios o también con 0xBB & 0xDC con hexadecimales.

Los bits a la izquierda que superen los 32 bits se descartan. Por ejemplo, si ejecutamos 12884902075 & 220 donde el valor del primer operando tiene a la izquierda dos bits uno que superan los 32 bits, tal como aparece resaltado en amarillo a continuación, vemos que son descartados, siendo de hecho el valor 187 para el primer operando como antes y generando el mismo resultado de la operación:

12884902075 =   1100000000000000000000000010111011
220 =             00000000000000000000000011011100
187 & 220 = 152 = 00000000000000000000000010011000

El primer bit a la izquierda o bit más significativo es el llamado bit de signo. Veamos los límites de estos números enteros, donde se observa que todos los números negativos tiene el primer bit a uno:

-2147483648  0b10000000000000000000000000000000  0x80000000
-255         0b11111111111111111111111100000001  0xFFFFFF01
-1           0b11111111111111111111111111111111  0xFFFFFFFF
 0           0b00000000000000000000000000000000  0x00000000
+1           0b00000000000000000000000000000001  0x00000001
+255         0b00000000000000000000000011111111  0x000000FF
+2147483647  0b01111111111111111111111111111111  0x7FFFFFFF

Los números negativos se manejan en complemento a dos. Por ejemplo, si JavaScript está operando -255 en operaciones a nivel de bit, toma el positivo 255, lo invierte con el operador NOT (~) y le suma 1:

          255 = 0b00000000000000000000000011111111  0x000000FF
         ~255 = 0b11111111111111111111111100000000  0xFFFFFF00
            1 = 0b00000000000000000000000000000001  0x00000001
~255+1 = -255 = 0b11111111111111111111111100000001  0xFFFFFF01

El complemento a dos garantiza que el primer bit será siempre uno cuando el número es negativo y cero en otro caso. Si aplicamos el complemento a dos a un negativo obtenemos el positivo:

         -255 = 0b11111111111111111111111100000001  0xFFFFFF01
        ~-255 = 0b00000000000000000000000011111110  0xFFFFFFFE
            1 = 0b00000000000000000000000000000001  0x00000001
~-255+1 = 255 = 0b00000000000000000000000011111111  0x000000FF

Vease que aplicar NOT a un número negativo es como sumarle 0xFFFFFFFF, suma que producirá 1 bit de acarreo a la izquierda que supera 32 bits que será ignorado en operaciones a nivel de bit:

~-255 =
~11111111111111111111111100000001 = 
 00000000000000000000000011111110

-255+0xFFFFFFFF =
 00000000000000000000000011111111
 11111111111111111111111111111111
─────────────────────────────────
100000000000000000000000011111110

En la implementación que haremos después manejaremos polinomios de 32 bits que pueden originar valores CRC negativos. Supongamos que obtenemos un valor CRC -255. Si hiciéramos (-255).toString(2) obtendríamos -0b11111111, -0xFF en hexadecimal. No podemos devolver este valor pues no es el verdadero binario que se esconde detrás del complemento a dos. Podemos deshacerlo con lo siguiente:

((-255)+0xFFFFFFFF+1).toString(2) =
(4294967041).toString(2) = 
"11111111111111111111111100000001"

Como 0xFFFFFFFF + 1 = 0x100000000 = 232 también podemos hacerlo así:

((-255)+Math.pow(2, 32)).toString(2) =
(4294967041).toString(2) =
"11111111111111111111111100000001"

Veamos un ejemplo usando el polinomio 0x814141AB (CRC-32/AIXM) de ancho 32 bits, generando en la tabla el índice decimal 122 (0x7A), exponiendo los números en hexadecimal para que no ocupen mucho espacio en pantalla. Observe que aparecen algunos resultados negativos:

j=0 ⇒  0x7A000000 << 1 =  -0xC000000        =  -0xC000000
j=1 ⇒  -0xC000000 << 1 = -0x18000000 ^ Poly =  0x694141AB
j=2 ⇒  0x694141AB << 1 = -0x2D7D7CAA        = -0x2D7D7CAA
j=3 ⇒ -0x2D7D7CAA << 1 = -0x5AFAF954 ^ Poly =  0x24444707
j=4 ⇒  0x24444707 << 1 =  0x48888E0E        =  0x48888E0E
j=5 ⇒  0x48888E0E << 1 = -0x6EEEE3E4        = -0x6EEEE3E4
j=6 ⇒ -0x6EEEE3E4 << 1 =  0x22223838 ^ Poly = -0x5C9C866D
j=7 ⇒ -0x5C9C866D << 1 =  0x46C6F326 ^ Poly = -0x38784D73

En la traza convertimos cada valor numérico en un string, en este caso usando toString(16). Se observa por ejemplo que el primer valor 0x7A000000 es el que se inicia con el índice 0x7A multiplicado por 224 (agregando 24 ceros). En binario es un número que empieza con 01111010 y le siguen tres bytes ceros. Como el primer bit es un cero se trata de un número no negativo. Al desplazar un bit a la izquierda, el primer byte será 11110100, con lo que el registro de 32 bits tiene un primer bit puesto a uno y por tanto es un número negativo. Cualquier representación de ese número, como usando toString(), se realizará aplicando el complemento a dos:

   n = 11110100 00000000 00000000 00000000 ⇒  F4000000
  ~n = 00001011 11111111 11111111 11111111 ⇒  0BFFFFFF
   1 = 00000000 00000000 00000000 00000001 ⇒  00000001
~n+1 = 00001100 00000000 00000000 00000000 ⇒ -0C000000

Por lo tanto el binario real resultado de la operación 0x7A000000 << 1 es 0xF4000000 y no la representación en complemento a dos -0xC000000. Mientras ejecutamos el algoritmo no es necesarios hacer nada, puesto que JavaScript usará el binario real con las operaciones a nivel de bit. Pero si hacemos una traza usando toString(2), o bien cuando devolvamos el CRC al final del algoritmo, hemos de deshacer el complemento a dos si el numero es negativo. En la traza anteponemos el signo "#" para indicar su valor binario real:

j=0 ⇒  0x7A000000 << 1 = #0xF4000000        = #0xF4000000
j=1 ⇒ #0xF4000000 << 1 = #0xE8000000 ^ Poly =  0x694141AB
j=2 ⇒  0x694141AB << 1 = #0xD2828356        = #0xD2828356
j=3 ⇒ #0xD2828356 << 1 = #0xA50506AC ^ Poly =  0x24444707
j=4 ⇒  0x24444707 << 1 =  0x48888E0E        =  0x48888E0E
j=5 ⇒  0x48888E0E << 1 = #0x91111C1C        = #0x91111C1C
j=6 ⇒ #0x91111C1C << 1 =  0x22223838 ^ Poly = #0xA3637993
j=7 ⇒ #0xA3637993 << 1 =  0x46C6F326 ^ Poly = #0xC787B28D
    

El negativo aparece como resultado de una operación a nivel de bit:

0x7A000000 = 2046820352
0x80000000 = 2147483648
0x7A000000 << 1 =         -0x0C000000 = -201326592
0x7A000000 | 0x80000000 = -0x06000000 = -100663296
0x7A000000 ^ 0x80000000 = -0x06000000 = -100663296
0x7A000000 + 0x80000000 =  0xFA000000 = 4194304000

Vease que la operaciones desplazamiento, OR y XOR generan un uno en el primer bit, generando un negativo. Mientras que la operación suma aritmética no funciona a nivel de bit y considera los números en formato de coma flotante (ver IEEE754). Observe a continuación como forzamos un negativo descubriendo el complemento a dos con la operación OR con un cero, mientras que la suma aritmética con un cero no modifica el valor:

(0xF4000000 + 0).toString(16) =  0xF4000000
(0xF4000000 | 0).toString(16) = -0x0C000000

En el apartado siguiente usaremos esto para saber cuando el primer bit es un uno.

Operadores de desplazamiento a nivel de bit en JavaScript

La operación desplazamiento a la derecha en JavaScript se ejecuta con el operador >>>. En los algoritmos basados en binarios en string hemos usado la función shiftRight(x, shift), donde x es un binario en string y shift es un número decimal con la cantidad de bits a desplazar:

function shiftRight(x="0", shift=0){
    return "0".repeat(shift) + x.substr(0, x.length-shift);
}

Usando el polinomio 0x814141AB con la entrada "123456789", en el byte i=3 con el algoritmo del apartado con binarios en string se realiza un desplazamiento de 24 bits a la derecha para obtener el crcTopByte usando esta función shiftRight():

crcTopByte =
shiftRight(crc, 24)  =
shiftRight("11101000000000010111001001011000", 24) =
"11101000"

Se observa que con esa operación obtenemos el primer byte de la izquierda. En la implementación del algoritmo que haremos en el siguiente apartado usando números, ejecutamos >>>, obvservando que el número es negativo pero se usa el número real sin complemento a dos, obteniéndose el mismo resultado:

crcTopByte =
crc >>> 24  =
#11101000000000010111001001011000 >>> 24 =
11101000

En JavaScript también existe el desplazamiento a la derecha conservando el signo >>, pero no es de aplicación puesto que estamos ignorando negativos. En cualquier caso el desplazamiento a la derecha se comporta igual en ambos casos.

El problema se plantea con el desplazamiento a la izquierda en JavaScript. Con binarios en string usamos la siguiente función:

function shiftLeft(x="0", shift=0) {
    return x.substr(shift) + "0".repeat(shift);
}

Esa función actúa sobre un registro cuya longitud viene dada por el argumento x. Si fuera necesario hay que pasar ceros a la izquierda para completar la longitud del registro. Mientras que en JavaScript tenemos el operador << que actúa siempre sobre un registro de 32 bits. Y esto supone una diferencia importante a tener en cuenta.

Por ejemplo, desplazar a la izquierda 3 bits sobre el binario en string "0011101111", que queremos que sea un registro de 10 bits para lo cual agreamos dos ceros a la izquierda:

shiftLeft("0011101111", 3) = "1101111000"

Con esa función el ancho del registro viene determinado por la longitud del primer argumento, por lo que los tres primeros bits desaparecen por la izquierda y se agregan tres ceros por la derecha. Al final el resultado seguirá teniendo una longitud de 10 bits. Mientras que en JavaScript el ancho siempre es de 32 bits:

0b00000000000000000000000011101111 << 3 =
0b00000000000000000000011101111000

Obviamente no es mismo resultado. Para eliminar los bits a la izquierda mayor del ancho w=10 que estamos considerando, podemos hacer lo siguiente:

(0b11101111 << 3) & (Math.pow(2, 10)-1) =
1101111000

Se trata de aplicar un máscara con w=10 unos, resultado de 2w-1 = 210-1 = 10000000000 - 1 = 1111111111, con lo que eliminamos los bits sobrantes de la izquierda:

n   =         00000000000000000000011101111000
210-1 =       00000000000000000000001111111111
n & (210-1) = 00000000000000000000001101111000

La otra complicación con el desplazamiento a la izquierda es que el número pudiera resultar negativo si el primer bit es un uno. Ya vimos antes que sólo debemos tenerlo en cuenta si vamos a dar salida a ese número con toString().

Por otro lado en el algoritmo con binarios en strings que hemos visto, cuando generabamos la tabla teníamos que comprobar que el primer bit era un uno. Como usábamos binarios en string era suficiente consultando n[0]==="1", dado que n era un string. En la implementación con números no podemos hacer eso pues manejaremos números. Podemos usar lo que vimos al final del apartado anterior: cuando el número es negativo entonces el primer bit es un uno. Bastaría consultar si (n|0) < 0, siempre y cuando n fuera un registro de w=32 bits, es decir, con polinomio de w=32 bits de ancho. Pero nuestros algoritmos deben prepararse para admitir polinomios de anchos inferiores a 32 bits. Así que usaremos ((n*Math.pow(2, 32-widthBits))|0) < 0. Se trata de agregar 32-w ceros a n, que tiene una longitud w, con lo que obtenemos un número binario de 32 bits y así podemos consultar si es negativo. Veamos un ejemplo.

w = 12 bits
n = 110101101101
n·232-12 = n·220 = 11010110110100000000000000000000
(11010110110100000000000000000000 | 0) < 0 ⇒ true

El número 110101101101 tiene el primer bit a uno en un registro de w=12 bits. Al multiplicar agregamos 20 ceros, más los 12 del número hacen un total de 32 bits, lo que produce un negativo al operar OR con cero.

Hay otra forma para consultar si el primer bits es uno: n >>> (widthBits-1) & 1. Si n = 110101101101 es el mismo número del ejemplo anterior con un ancho w=12 bits, al desplazar 12-1 = 11 bits a la derecha su primer bit quedará ubicado en el bit menos significativo del registro de 32 bits de JavaScript. Consultando con un AND 1 sabremos si es o no un uno.

Implementación JavaScript del algoritmo CRC con números binarios

Con los visto en los apartados anteriores vamos a acometer la implementación en números binarios de JavaScript. Presentamos directamente el algoritmo siguiente, que no deja de ser el mismo que el visto en el primer apartado usando strings, pero ahora ajustándolo a números:

function crcTableBasic({arrayBytes=[], width=0, poly="0"}){
    let widthBits = Math.max(width, 8);
    poly = Number(`0x${poly}`) * Math.pow(2, widthBits-width);
    let table = [];
    for (let i=0; i<256; i++){
        let n = i * Math.pow(2, widthBits-8);
        for (let j=0; j<8; j++){
            let shifted = (n<<1) & (Math.pow(2, widthBits)-1);
            //también if (((n*Math.pow(2, 32-widthBits))|0) < 0)
            if (n>>>(widthBits-1) & 1) {
                n =  shifted ^ poly;
            } else {
                n = shifted;
            }
        }
        table.push(n);
    }
    let crc = 0;
    for (let i=0; i<arrayBytes.length; i++){
        let Byte = arrayBytes[i];
        let crcTopByte = crc >>> (widthBits-8);
        let index = crcTopByte ^ Byte;
        let tab = table[index];
        let crcShift = (crc<<8) & (Math.pow(2, widthBits)-1);
        crc = crcShift ^ tab;
    }
    if (crc<0) crc += Math.pow(2, 32);
    crc = crc / Math.pow(2, widthBits-width);
    return crc;
}

El argumento poly nos trae el polinomio en un string con valor hexadecimal. Lo convertimos a número con Number(`0x${poly}`) y lo multiplicamos por Math.pow(2, widthBits-width) para ajustarlo a polinomios con anchos inferiores a 8. Como widthBits = Math.max(width, 8) entonces lo anterior agrega ceros cuando el ancho del polinomio es inferior a 8 bits. Todo esto hace lo mismo que lo visto con strings hexToBin(poly).padStart(width, "0").padEnd(widthBits, "0").

A continuación entramos en el bucle que genera la tabla. El número n se multiplica por Math.pow(2, widthBits-8), pues debe tener el tamaño del polinomio. Dentro del bucle interno hay un desplazamiento a la izquierda, que ajustamos al ancho del polinomio con (n<<1) & (Math.pow(2, widthBits)-1), tal como vimos en el apartado anterior sobre la eliminación de los bits que sobresalen del registro de ancho widthBits por la izquierda. La consulta sobre si el primer bit es un uno la hacemos con n>>>(widthBits-1) & 1, ya explicado al final del apartado anterior. Incluimos un comentario con la otra forma de hacerlo. Dentro del bucle que itera por los bytes sólo hay que comentar el ajuste del desplazamiento a la izquierda, pues en el resto no hay que ajustar nada.

Al salir del bucle tenemos ya el CRC, que si fuera negativo deshacemos el complemento a dos como ya vimos en apartados anteriores. Finalizamos deshaciendo el ajuste inicial para polinomios inferiores a 8 bits, pues si al inicio multiplicamos el polinomio por Math.pow(2, widthBits-width), ahora dividimos el CRC por la misma cantidad. En esencia al inicio habíamos agregado widthBits-width ceros y ahora los quitamos.

Veamos una traza del CRC-24/LTE-A, polinomio de ancho w=24 bits, usando la entrada "123456789", presentando sólo la iteración del tercer byte (i=2) igual que lo expuesto al final del primer apartado:

i=2 ⇒ byte = arrayBytes[2] =  00110011
crcTopByte = crc >>> 16 =  101101111000110010010001 >>> 16 = 10110111
index = byte ^ crcTopByte =  00110011 ^  10110111 =  10000100 (132)
tab = table[index] =  101000001010000101000101 ⇒  0xA0A145
crcShift = crc << 8 =  101101111000110010010001 << 8 =  100011001001000100000000
crc = crcShift ^ table[index] =  100011001001000100000000 ^  101101111000110010010001 =
      001011000011000001000101 ⇒  0x2C3045

Se obtiene el mismo CRC parcial 0x2C3045 que con el algoritmo con binarios en string. Y al trabajar con números es más eficiente que el anterior que trabaja con strings. Pero tiene una limitación, pues con numeros binarios sólo podemos llegar hasta CRC de 32 bits, mientras que con strings no tenemos limitación de longitud. De todas formas en el tema siguiente veremos un algoritmo para generar CRC de cualquier longitud con números en JavaScript.

Invirtiendo los bits de un binario en JavaScript

El algoritmo anterior trabaja con números binarios en JavaScript y es más eficiente que el que trabaja con binarios en string del primer apartado. Podríamos afinar aún más evitando los ajustes que nos imponen los desplazamientos a la izquierda o la consulta del primer bit. Para ello antes vamos a ver como podemos invertir un número binario. Si tenemos el binario 00110101 y lo invertimos resultará 10101100. Esto parece fácil hacerlo manualmente. Y de hecho también es sencillo llevarlo a cabo si el binario es un string:

function reverse(x="0", width=0){
    x = x.replace(/^0+/, "") || "0";
    return [...x.padStart(width, "0")].reverse().join("");
}

Lo anterior convierte el string en un array de caracteres y luego lo invierte usando el método reverse() de Array, volviendo a unir sus caracteres con el método join().

Para invertir un binario es importante especificar su ancho. Por ejemplo, si tenemos el binario 110 y aplicamos inversiones de varios anchos obtenemos números diferentes:

3  110      011
4  0110     0110
5  00110    01100
6  000110   011000

Implementamos reverse() con números de la siguiente forma:

function reverse(num=0, width=0) {
    let reversed = 0;
    for (let i=0; i<width; i++) {
        let x = (num >>> i) & 1;
        //También reversed += x * Math.pow(2, width-1-i);
        reversed = x | (reversed << 1);
    }
    return reversed;
}

Iteramos por los bits del ancho w (width en el código) tomando el bit que está a la derecha en cada paso y lo guardamos en x. Lo incorporamos por la izquierda de dos formas posibles. Una de ellas se basa en multiplicar ese bit x, que puede ser un cero o un uno, por la potencia del lugar de la izquierda x·2w-1-i. Si por ejemplo w = 8 y el primer bit de la derecha es un uno (posición i=0), entonces para situarlo a la izquierda hacemos 1·28-1-0 = 27 que es el binario r=10000000, ubicando el uno al inicio del ancho w=8. El siguiente bit, cero o uno, se multiplica por 26 y se suma al r obtenido antes. Y así sucesivamente. Esta forma es la que aparece en la línea en comentario del código anterior.

La segunda forma es desplazando el invertido r (reversed en el código) una posición a la izquierda y haciendo un OR con el bit extraído. Si tuviéramos en un momento dado del bucle r = 10101 y el siguiente bit extraído es un cero, entonces hacemos 1 | (r << 1) = 1 | (10101 << 1) = 1 | 101010 = 101011. Recuerde que el desplazamiento izquierda es sobre el registro de 32 bits de JavaScript.

La siguiente traza muestra como evoluciona el bucle para las dos opciones, obteniéndose al final del bucle el mismo binario:

n: 00110101 (num)
w: 8 (width)
r: 0 (reversed)
x: (n >>> i) & 1

i   x   x|(r<<1)    r+x·2w-1-i
-----------------------------
0   1   1           10000000
1   0   10          10000000
2   1   101         10100000
3   0   1010        10100000
4   1   10101       10101000
5   1   101011      10101100
6   0   1010110     10101100
7   0   10101100    10101100

Quizás es preferible la opción x | (reversed << 1) dado que la otra usa operaciones aritméticas que pueden ser más lentas.

Algoritmo CRC reflejado optimizado para JavaScript

En el primer apartado vimos como obtener el resto de una forma simplificada. Como ejemplo usamos la entrada index = 01111010, 0x7A en hexadecimal, 122 en decimal, letra "z" en ASCII. Y que el polinomio era 0x9B con un ancho w = 8 bits (CRC-8/LTE). Agregando el 1 inicial es poly = (1)10011011. Obteníamos el resultado de mod(08, poly, index) = mod(08, 110011011, 01111010) = 00101010 usando una simplificación del algoritmo donde prescindíamos del uno inicial del polinomio:

Poly 10011011 ⇒  0x9B
Trace for Index = 0b01111010, 0x7A, 122 : 
j=0 ⇒ 01111010 << 1 = 11110100        = 11110100
j=1 ⇒ 11110100 << 1 = 11101000 ^ Poly = 01110011
j=2 ⇒ 01110011 << 1 = 11100110        = 11100110
j=3 ⇒ 11100110 << 1 = 11001100 ^ Poly = 01010111
j=4 ⇒ 01010111 << 1 = 10101110        = 10101110
j=5 ⇒ 10101110 << 1 = 01011100 ^ Poly = 11000111
j=6 ⇒ 11000111 << 1 = 10001110 ^ Poly = 00010101
j=7 ⇒ 00010101 << 1 = 00101010        = 00101010

Si invertimos el polinomio sin el uno inicial tenemos Poly reversed = 11011001. Si invertimos la entrada tenemos Index reversed = 01011110. Si en lugar de utilizar el desplazamiento izquierda usamos el derecha, el algoritmo ejecutará esto:

Poly reversed 11011001 ⇒  0xD9
Trace for Index reversed = 0b01011110, 0x5E, 94: 
j=0 ⇒ 01011110 >>> 1 =  00101111        =  00101111
j=1 ⇒ 00101111 >>> 1 =  00010111 ^ Poly =  11001110
j=2 ⇒ 11001110 >>> 1 =  01100111        =  01100111
j=3 ⇒ 01100111 >>> 1 =  00110011 ^ Poly =  11101010
j=4 ⇒ 11101010 >>> 1 =  01110101        =  01110101
j=5 ⇒ 01110101 >>> 1 =  00111010 ^ Poly =  11100011
j=6 ⇒ 11100011 >>> 1 =  01110001 ^ Poly =  10101000
j=7 ⇒ 10101000 >>> 1 =  01010100        =  01010100

Se observa la exacta simetría de ambos algoritmos. Cada resto parcial de esta ejecución con polinomio y entrada invertido es un fiel reflejo del de la ejecución sin inversión. Usamos desplazamientos a la derecha que son menos problemáticos en JavaScript. Además vemos que se suma XOR con el polinomio cuando el bit de la derecha es un uno (resaltados en amarillo), lo nos facilitará comprobar si ese bit es un uno.

Figura
Figura. Esquema algoritmo CRC reflejado de 24 bits con tabla

Apliquemos esto al algoritmo para obtener el CRC que se presenta esquemáticamente en la Figura. La entrada Input reversed es invertida, es decir, cada byte se invierte con reversed(Byte, 8) antes de tratarlo. El registro que contiene el CRC también está invertido, por lo que tomaremos el byte menos significativo o byte de la derecha como crcTopByte. Esto lo conseguimos con algo tan simple como CRC & 0xFF.

Hacemos, como antes, la suma XOR entre el byte y el index para obtener el valor de la tabla. Desplazamos 8 bits a la derecha el CRC y lo sumamos XOR con el resultado de la tabla, siendo este el nuevo valor del CRC para el siguiente byte de la entrada.

La implementación del algoritmo reflejado es la siguiente:

function crcTableReverseBasic({arrayBytes=[], width=0, poly="0"}){
    let widthBits = Math.max(width, 8);
    poly = reverse(Number(`0x${poly}`), width);
    let table = [];
    for (let i=0; i<256; i++){
        let n = i;
        for (let j=0; j<8; j++){
            let shifted = n >>> 1;
            if (n & 1===1) {
                n = shifted ^ poly;
            } else {
                n = shifted;
            }
        }
        table.push(n);
    }
    let crc = 0;
    for (let i=0; i<arrayBytes.length; i++){
        let Byte = reverse(arrayBytes[i], 8);
        let crcTopByte = crc & 0xFF;
        let index = crcTopByte ^ Byte;
        let tab = table[index];
        let crcShift = crc >>> 8;
        crc = crcShift ^ tab;
    }
    crc = reverse(crc, width);
    if (crc<0) crc += Math.pow(2, 32);
    return crc;
}

Compare la parte que genera la tabla con la versión anterior sin reflejar:

//Versión sin reflejar para generar la tabla
poly = Number(`0x${poly}`) * Math.pow(2, widthBits-width);
let table = [];
for (let i=0; i<256; i++){
    let n = i * Math.pow(2, widthBits-8);
    for (let j=0; j<8; j++){
        let shifted = (n<<1) & (Math.pow(2, widthBits)-1);
        if (n>>>(widthBits-1) & 1) {
            n =  shifted ^ poly;
        } else {
            n = shifted;
        }
    }
    table.push(n);
}

Ahora hay que invertir el polinomio, pero no es necesario multiplicarlo por Math.pow(2, widthBits-width) para ajustar los polinomios a múltiplos de 8, pues estos ceros agregados quedarán a la izquierda y se desprecian. De igual forma no necesitaremos multiplicar cada byte entre 0 y 255 por Math.pow(2, widthBits-8). Ni ajustar el desplazamiento izquierda pues tenemos un desplazamiento derecha. Y en lugar de detectar si el bit más significativo es un uno, detectaremos que el bit menos significativo sea un uno, lo que se hace con n & 1===1 de forma muy simple.

Compare el bucle que itera por los bytes de la entrada y las operaciones de salida que devuelven el CRC con la versión anterior sin reflejar:

//Versión sin reflejar del bucle de la entrada y devolución CRC
for (let i=0; i<arrayBytes.length; i++){
    let Byte = arrayBytes[i];
    let crcTopByte = crc >>> (widthBits-8);
    let index = crcTopByte ^ Byte;
    let tab = table[index];
    let crcShift = (crc<<8) & (Math.pow(2, widthBits)-1);
    crc = crcShift ^ tab;
}
if (crc<0) crc += Math.pow(2, 32);
crc = crc / Math.pow(2, widthBits-width);
return crc;

Ahora hay que invertir el byte de la entrada, pero el crcTopByte es ahora el byte de la derecha del CRC, que se obtiene fácilmente con crc & 0xFF. Ni hay que ajustar el desplazamiento a la izquierda para obtener crcShift, pues ahora es un desplazamiento derecha. Con la versión reflejada antes de devolver el CRC tenemos que invertirlo para deshacer el reflejo del algoritmo. Pero no necesitamos deshacer el agregado de ceros como si hacemos en la versión sin reflejar.

Las operaciones con la versión reflejada son más simples. El único inconveniente es invertir con reverse() el polinomio, cada byte de la entrada y el CRC final. En un tema posterior veremos que esto es una ventaja en ciertos casos.

Veamos la ejecución de un ejemplo que ya hemos visto con los dos algoritmos anteriores de este tema. Se trata del CRC-24/LTE-A, polinomio de ancho w=24 bits, usando la entrada "123456789", presentando sólo la iteración del tercer byte (i=2):

i=2 ⇒ byte = arrayBytes[2] =  00110011 ⇒ byte = reverse(byte) =  11001100
crcTopByte = crc & 0xFF =  100010010011000111101101 &  11111111 =  11101101
index = byte ^ crcTopByte =  11001100 ^  11101101 =  00100001
tab = table[index] =  101000101000010100000101
crcShift = crc >>> 8 =  100010010011000111101101 >>> 8 =  000000001000100100110001
crc = crcShift ^ tab =  000000001000100100110001 ^ 101000101000010100000101 =
      101000100000110000110100 ⇒  0xA20C34

Si invertimos este resultado parcial reverse(101000100000110000110100, 24) obtendremos el mismo CRC parcial 0x2C3045 que con los dos algoritmos anteriores vistos en este tema.

El interior del bucle que itera por los bytes de la entrada puede simplificarse en una única línea con crc = (crc >>> 8) ^ table[Byte ^ (crc & 0xFF)], donde el byte es invertido previamente y el CRC es también el invertido. Si vemos algo como esto cuando empezamos a estudiar como funcionan los algoritmos para generar el CRC nos sentiremos algo confusos, tal como expusimos al inicio de esta serie de temas. Ahora ya estamos en condiciones de entenderlo.

Pero la cosa no acaba aquí. Aún nos falta un siguiente tema, pues sobre este último algoritmo hay varias cosas más que necesitamos hacer.