(void *) blog

Posted on by fortytwo_de


Algoritmo

El algoritmo para convertir una cadena a Base64 es:

  • Convertir una secuencia de caracteres a una de números enteros, cuyo valor será su número ASCII.
  • Cambiar de base los números, de base 10 a base 2 (binario).
  • Agrupar los números de 3 en 3, en grupos de 24 bits. Si el número de números no es divisible entre tres, se añadirán bits de padding.
  • Dividir cada grupo de 24 bits en cuatro grupos de 6 bits.
  • Convertir de los números de los grupos anteriores a base 10.
  • Asignar a cada número la letra que le corresponde en el alfabeto de base64.

Por ejemplo, para codificar LOL:

  • Se toman los valores ASCII de cada una de las letras. En este caso: 76, 79, 76.
  • Cambiando de base: 01001100 | 01001111 | 01001100

Para dividir este grupo de 24 bits en cuatro de 6 bits, necesitamos hacer operaciones con los bits. Explicaré brevemente las cuatro operaciones bitwise necesarias.

Logical left shift

Consiste en mover hacia la izquierda un número de bits, añadiendo n bits cero a la derecha del número, convirtiendo bits menos significativos en bits más significativos. Por ejemplo:

   10001110
<<        2
-----------
   00111000

Es importante observar que el bit más significativo se descarta siempre, por lo que las operaciones bitwise lógicas sólo se deben realizar en tipos unsigned, o se perderá el bit de signo.

Logical right shift

Similar al left shift, se añade un número n de bits al número, pero a la izquierda: se descartan los bits menos significativos.

   10001110
>>        2
-----------
   00100011

Logical AND
Una de las operaciones lógicas más simples. Sólo es 1 si los dos números que está comparando son 1.

  00001010
& 00001111
----------
  00001010

Es muy útil para extraer unos bits concretos en un número.

Logical OR

Esta operación lógica tendrá como resultado 1 si cualquiera de los números son 1.

  00001010
| 10100000
----------
  10101010

Se utilizará para "juntar" dos números binarios.


Conocidas las operaciones binarias que necesitamos para obtener los cuatro grupos de 6 bits, se definen los cuatro grupos como A, B, C, D: AAAAAABB | BBBBCCCC | CCDDDD. En el ejemplo de LOL:

010011 00 | 0100 1111 | 01 001100
------ --------- --------- ------
  A        B         C       D

De esto deducimos la composición binaria de los grupos de 6 bits:

  • El primer grupo está formado por los 6 bits más significativos del primer número.
  • El segundo grupo está formado por los 2 bits menos significativos del primer número y los 4 bits más significativo del segundo número.
  • El tercer grupo está formado por los 4 bits menos significativos del segundo número y los 2 bits más significativos del tercer número.
  • El cuarto grupo está formado por los 6 bits menos significativos del tercer número.

Primer grupo

El primer grupo, A, es fácil de obtener, sólo hay que hacer right shift de 2 bits.

  01001100
>>       2
----------
  00010011

Segundo grupo

El segundo grupo es más complicado. Está compuesto por los 2 bits menos significativo del primer número y los 4 bits más significativos del segundo número. Para extraer los dos bits menos significativo del primer grupo, se realiza la operación AND 00000011 (también conocido como bitmask).

  01001100
& 00000011
----------
  00000000

En este caso concreto los 2 bits menos significativo del primer número son 00. Estos se convertirán en los dos bits más significativos del segundo grupo de 6 bits. Para obtener los 6 bits restantes, que son los 4 más significativos del segundo número, se tiene que hacer, igual que con el primer grupo, un right shift, pero de 4 bits.

  01001111
>>       4
----------
  00000100

Por lo tanto, el segundo grupo de 6 bits será la unión (operación OR) de los 2 bits menos significativos del primer número con los 4 bits más significativos del segundo número. Pero para que los bits menos significativos del primer grupo estén en la posición que les corresponde, hay que hacer un left shift de 4 bits, lo que los convertirá en los bits más significativos del segundo grupo.

Nota: En este caso los bits menos significativos del primer número son 00, así que los marcaré en cursiva para que se vea el efecto del left shift.

  00000000
<<       4 
----------
  00000000

Finalmente, para el segundo grupo, se realiza la operación OR:

  00000000
| 00000100
----------
  00000100

Para aclarar toda la confusión, y recapitulando: el segundo grupo se obtiene realizando la operación (triplet_1 & 0b00000011) << 4 | (triplet_2 >> 4).


Tercer grupo

El tercer grupo de 6 bits está formado por los 4 bits menos significativos del segundo número y los 2 bits más significativos del tercer número. Para obtener los 4 bits menos significativos del segundo número aplicamos una bitmask 0b00001111.

  01001111
& 00001111
----------
  00001111

Puesto que estos bits van a ser los más significativos del tercer grupo, hay que aplicar un left shift de 2 bits.

  00001111
<<       2
----------
  00111100

Los 2 bits menos significativos vendrán de los 2 bits más significativos del tercer número, así que se puede extraer fácilmente con un right shift de 6 bits.

  01001100
>>       6
----------
  00000001

Finalmente, se compone el tercer grupo con una operación OR:

  00000001 
| 00111100
----------
  00111101

Recapitulando: para obtener el tercer grupo, se realiza la operación (triplet_2 & 0b00001111) << 2 | (triplet_3 >> 6)


Cuarto grupo

El último grupo está compuesto únicamente por los 6 bits menos significativos del tercer número, así que es trivial extraerlos con una bitmask 0b00111111:

  01001100
& 00111111
----------
  00001100

Resumen
  • Primer grupo: triplet_1 >> 2
  • Segundo grupo: (triplet_1 & 0b00000011) << 4 | (triplet_2 >> 4)
  • Tercer grupo: (triplet_2 & 0b00001111) << 2 | (triplet_3 >> 6)
  • Cuarto grupo: (triplet_3 & 0b00111111)

Show me the code
#include 
#include 
#include 
 
char b64(int pos) {
	char* b64dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
	if(pos == 0) return '='; // char, not a string literal.
	if(pos <= strlen(b64dict)) 
		return b64dict[pos];
}
 
void b64_convert_triplet(char* input) {
    int a = 0, b = 0, c = 0, d = 0;
    int i = 0;
    int mode = 0;
    char* triplet = input; // verbatim copy of input
    
    while(*input) {
        mode = i % 3;
        
        if(mode == 0) {
            a = triplet[0] >> 2;
        } else if(mode == 1) {
            b = (triplet[0] & 0x03) << 4 | (triplet[1] >> 4); // 0x3 = 0b00000011
        } else if(mode == 2) {
            c = (triplet[1] & 0x0f) << 2 | (triplet[2] >> 6); // 0x0f = 0b00001111
            d = (triplet[2] & 0x3f); // 0x3f = 0b00111111
        }
    
        i++;
        *input++;
    }
    
    if(mode == 1) { // two-char group: needs 2 bits of padding
        c = (triplet[1] & 0x0f) << 2;
    }
    
    if(mode == 0) { // single-char group: needs 4 padding bits
        b = (triplet[0] & 0x03) << 4;
    }
    
    printf("%c%c%c%c", b64(a), b64(b), b64(c), b64(d));
}
 
int main(int argc, char** argv) {
        char* to_convert = malloc(sizeof(char) * 102);
        to_convert[0] = '\0';
        char* buffer = malloc(sizeof(char) * 5);
        buffer[0] = '\0';
        char* append_char = malloc(sizeof(char) * 2);
        append_char[0] = '\0';
        
        int i = 0;
        int mode = 0;
        scanf("%s\n", to_convert);
        
        while(*to_convert) {
            mode = i % 3;
            
            sprintf(append_char, "%c", *to_convert);
            buffer = strcat(buffer, append_char);
            
            if(mode == 2) {
                b64_convert_triplet(buffer);
                i = 0;
                buffer[0] = '\0';
            }
            
            *to_convert++;
            i++;
        }
        if(mode != 2) b64_convert_triplet(buffer);
        printf("\n");
        return 0;
}

Descarga el código (pastie.org).
El proceso inverso (cadena legible-Base64) queda como un ejercicio para el lector. Bueno, y que estoy cansado de hacer dibujitos ASCII también influye.

Posted on by fortytwo_de | Posted in Algoritmos, C, Programación


2 Responses to Base64

  1. rf1x says:


    ¿”Bits de padding” es una manera elegante de decir que si el número de bits no es múltiplo de 3, dejas el resto ahí tirados sin hacer nada con ellos?


  2. Cash Advance Loan says:


    noteworthy click the up coming website


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>