Base64 selbst machen



  • Hallo zusammen,

    ich programmiere schon ne weile, allerdings viel mehr mit der Windows API und java. Mit Bitoperatoren komme ich bisher fast nicht in berührung.

    Deswegen möchte ich jetzt gern mal Base64 selbst programmieren.

    Den Algorithmus verstehe ich, allerings komme ich schon beim umsetzen sofort in schwierigkeiten da ich mit dem Shiften bzw. AND nicht klar komm.

    Beim Base 64 will ich ja immer 6 Bits.

    Beispiel wäre:

    ABC = 97 , 98 , 99 Dez

    Binär = 01000001 , 01000010 , 01000011

    Wenn ich draus jetzt Base64 mache muss ich ja folgendes tun:
    010000 01 , 0100 0010 , 01 000011

    010000 -> Q
    01 0100 -> U
    0001001 -> J
    100011 -> D

    Nur Wie mache ich das jetzt mit Code?
    also das Q bekomme ich noch raus indem ich den ersten buchstbe AND 0XFC -> 11111100 mache? Aber dann muss ich ja die letzten beiden und die nächsten 4 zusamme bekommen. Wie macht man das denn sinnvoll?



  • Du solltest zuerst einmal verstehen, dass Base64 jeweils drei aufeinander-folgende Eingabe-Bytes (24-Bit Nutzdaten) in vier aufeinander-folgende ASCII-Zeichen (32-Bit Text) umwandelt:

    Siehe:
    http://upload.wikimedia.org/wikipedia/de/7/7e/Base64.png

    Beachte dass, wenn die Länge der Eingabe (in Bytes) kein exaktes Vielfaches von drei ist, dann werden je nach Bedarf ein oder zwei NULL-Bytes ans Ende der Nachricht gepadded.

    Es somit nur 2^24 Eingabe-Möglichkeiten gibt (pro 3-Byte Block, vesteht sich), könnte man das ganze zum Beispiel mit einer Lookup-Tabelle lösen...



  • ich weiß schon 😉 das mit der lookup tabelle hab ich auch schon gegoogelt.

    mir geht es hier wirklich nur um die bitoperationen... wie ich verunden bzw. shiften muss, damit ich die jeweiligen bits bekomme

    z.B char a = 'A'

    Daraus wird ja "QQ==", Warum ist mir klar, aber nicht wie die Bitoperationen aussehen um a zu shiften um dann aus der tabelle die Buchstaben zu holen.

    ich weiß nicht wie ich mich ausdrücken soll



  • Kennst du denn schon die Bitoperationen &, | und ~ sowie << und >>, s. z.B. Bitoperationen?

    Für die ersten beiden Zahlen zeige ich es dir mal:
    (seien b1, b2 und b3 die drei Eingabe-Bytes, dann sind c1, c2, c3 und c4 die Indizes der Base64-Tabelle (0-63))

    unsigned int c1 = b1 >> 2; // um zwei Bits nach rechts verschoben (links mit Nullen aufgefüllt)
    unsigned int c2 = ((b1 & 0x03) << 4) | (b2 >> 4); // das erste Byte ausmaskiert und nach links verschoben,
                      // das 2. Byte nach rechts verschoben (die oberen 4 auf die unteren 4 Bits) und beides miteinander ver'oder't.
    

    (ich hoffe, ich habe jetzt keinen Fehler gemacht 😉
    So dann probiere mal die restlichen beiden c3 und c4 ähnlich zu codieren...



  • Dieser Code zeigt alle bits eines char nacheinander an:

    char x = 'A'; //== 0x41 == 01000001
    	for(int i = 7; i >= 0; i--)
    	{
    		printf("%c", ((x >> i) & 0x01) ? '1' : '0');
    	}
    	printf("\n");
    

    Durch das UND (&&) mit dem Wert 0x01 bekommst Du nur dass niederwertigste Bit.

    Also "foo && 0x01" ergibt entweder 0x00 oder 0x01, je nach dem, ob das niederwertigste Bit von 'foo' gesetzt ist oder nicht.

    Mit dem Schift-Operator (>>) können wir nach und nach alle Bits auf diese Weise durch testen...



  • DeathCubeUK schrieb:

    Dieser Code zeigt alle bits eines char nacheinander an:

    char x = 'A'; //== 0x41 == 01000001
    	for(int i = 7; i >= 0; i--)
    	{
    		printf("%c", ((x >> i) & 0x01) ? '1' : '0');
    	}
    	printf("\n");
    

    Durch das UND (&&) mit dem Wert 0x01 bekommst Du nur dass niederwertigste Bit.

    Also "foo && 0x01" ergibt entweder 0x00 oder 0x01, je nach dem, ob das niederwertigste Bit von 'foo' gesetzt ist oder nicht.

    Mit dem Schift-Operator (>>) können wir nach und nach alle Bits auf diese Weise durch testen...

    Sorry, ich meinte natürlich das binäre UND (&), nicht das logische UND (&&).



  • danke für eure antworten.

    Ich habe noch richtig Probleme mit Bit-Rechnung
    Ich hab ein sehr komisches Problem:

    Das hier geht:

    static const std::string base64_chars = 
                 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                 "abcdefghijklmnopqrstuvwxyz"
                 "0123456789+/";
    
    char c1 = base64_chars[ *c >> 2 ];
    
    		unsigned int test = ((*c) & 0x03) << 4;
    		unsigned int test2 = ( *(++c) >> 4);
    		char c2 = base64_chars[ test + test2 ];
    		c2 = base64_chars[ test | test2]; // gleiche wie davor nur test
    
    // c2 == U --> OK!
    

    Das hier nicht:

    char c2 = base64_chars[ ( (((*c) & 0x03) << 4 ) | ( *(++c) >> 4) ) ];
    
    // c2 == k verstehe aber nicht warum
    

    Könnt Ihr mir bitte weiterhelfen?



  • achso der input String ist "ABC"



  • Jetzt bin ich mit meinem latain am ende ^^

    das hier Funktioniert auch:

    const char* p1 = c;
    		const char* p2 = c++;
    		unsigned int bla = ( ((*p1) & 0x03) << 4 ) + ( (*p2) >> 4) ;
    

    aber ich verstehe den unterschied nicht... geht *c und *(++c) in einer Zeile nicht richtig?



  • leoni_ schrieb:

    Jetzt bin ich mit meinem latain am ende ^^

    das hier Funktioniert auch:

    const char* p1 = c;
    		const char* p2 = c++;
    		unsigned int bla = ( ((*p1) & 0x03) << 4 ) + ( (*p2) >> 4) ;
    

    aber ich verstehe den unterschied nicht... geht *c und *(++c) in einer Zeile nicht richtig?

    ** *c gibt Dir den Wert an der Speicher-Adresse zurück, auf die der Zeiger c **gerade zeigt.

    ** *(++c) macht im Prinzip das selbe, schiebt den Zeiger c **aber gleichzeitig (und zwar bevor der Wert gelesen wird!) um eine Position weiter, d.h. Du bekommst schon den Wert an der "neuen" Adresse.

    Analog würde** *(c++) ebenfalls c **um eine Position weiter schieben, aber noch den Wert der "alten" Adresse zurück liefern.

    Achtung: Von der Verwendung von** *c und *(++c) bzw. *(c++) **innerhalb einer Anweisung ist abzuraten, da die Auswertungsreihenfolge der Argumente nicht unbedingt definiert ist!

    http://stackoverflow.com/questions/24326572/pre-increment-operators-when-using-the-variable-on-the-same-line



  • Danke für deine Antwort,

    hmm das ist schon richtig. ich will ja da an den nächsten character. Und ich erhöhe mit absicht vorher, damit ich dann das B bekomme.

    Warum das nicht in einer Zeile geht, verstehe ich trotzdem nicht.



  • Hast Du meinen Edit bemerkt? 😕

    DeathCubeK schrieb:

    Achtung: Von der Verwendung von** *c und *(++c) bzw. *(c++) **innerhalb einer Anweisung ist abzuraten, da die Auswertungsreihenfolge der Argumente nicht unbedingt definiert ist!

    http://stackoverflow.com/questions/24326572/pre-increment-operators-when-using-the-variable-on-the-same-line

    Folgender Testcode:

    int _tmain(int argc, _TCHAR* argv[])
    {
    	const char *c = &test[0];
    	printf("%c %c\n", *c, *(++c));
    	return 0;
    }
    

    ...erzeugt bei mir folgende Ausgabe:

    b b
    

    😮

    (BTW: "Innerhalb einer Zeile" spielt für C/C++ keine Rolle, da Zeilenumbrüche für den Compiler keine Bedeutung haben und daher völlig optional sind. Es geht um Anweisungen, welche mit Semikolon abgeschlossen/getrennt werden)



  • Vielen Dank für deine Ausführliche Antwort.

    Ich bin jetzt scho am decodieren.

    Ich muss ja jetzt zurück rechnen. D.h. ich muss einen Kommenden Buchsten (Jetzt das Q) wissen welche Position es in der Tabelle hat.

    Das könnte ich jetzt mit Suchen machen oder ich nehme mir die Werte und mach Vergleiche. z.B. A = 65 --> 65-65 --> 0, B = 66 --> 66-65 = 1 usw.

    Ich hab schon gegoogelt aber irgenwie find ich nichts. Wie teuer sind den Vergleichsoperationen gegenüber einer Suche. Ich denke das Vergleichsoperationen von zwei int Variablen viel geringer ist als eine Suche. Aber ich würde es echt gern wissen. Ich weiß aber nicht nach welchen Stichwort ich suchen muss.



  • leoni_ schrieb:

    Vielen Dank für deine Ausführliche Antwort.

    Ich bin jetzt scho am decodieren.

    Ich muss ja jetzt zurück rechnen. D.h. ich muss einen Kommenden Buchsten (Jetzt das Q) wissen welche Position es in der Tabelle hat.

    Das könnte ich jetzt mit Suchen machen oder ich nehme mir die Werte und mach Vergleiche. z.B. A = 65 --> 65-65 --> 0, B = 66 --> 66-65 = 1 usw.

    Ich hab schon gegoogelt aber irgenwie find ich nichts. Wie teuer sind den Vergleichsoperationen gegenüber einer Suche. Ich denke das Vergleichsoperationen von zwei int Variablen viel geringer ist als eine Suche. Aber ich würde es echt gern wissen. Ich weiß aber nicht nach welchen Stichwort ich suchen muss.

    Mach Dir eine Lookup-Tabelle (Array) und verwende das Zeichen, also z.B. 'Q' (was nichts anderes als der Wert 0x51 ist, siehe ASCII-Tabelle), direkt als Index.

    Beispiel:

    int LUT[256];
    
    //Initialisierung der LUT - einmalig am Programmstart auszuführen!
    void init(void)
    {
       LUT['Q'] = 666; //Hier welchen Wert auch immer Du 'Q' zuweisen möchtest
    
       //Und so weiter für alle (relevanten) Zeichen...
    }
    
    //Funktion um für ein Eingabe-Zeichen den zugehörigen Wert abzufragen
    int getValue(const char c)
    {
       return LUT[c];
    }
    


  • das verstehe ich jetzt nicht...

    Ich hab doch 64 Werte und dann muss ich jedesmal nach dem jeweiligen Char suchen?

    Ich könnte das aber auch easy umrechnen.



  • ich hab nochmal drüber nachgedacht habs kapiert... aber dann muss ich alle werte initalisieren... hmm.



  • leoni_ schrieb:

    ... aber dann muss ich alle werte initalisieren... hmm.

    Einmalig, ja! Und man kann das natürlich mit einer Schleife elegant lösen 😉

    void init(void)
    {
       char c = 'A';
       for(int i = 0; i < 64; i++)
       {
          LUT[c] = i;
          c++;
       }
    }
    

    Danach steht in der Deiner LUT:

    LUT['A'] == 0 , LUT['B'] == 1 , LUT['C'] == 2 , und so weiter...



  • DeathCubeK schrieb:

    leoni_ schrieb:

    ... aber dann muss ich alle werte initalisieren... hmm.

    Einmalig, ja! Und man kann das natürlich mit einer Schleife elegant lösen 😉

    void init(void)
    {
       char c = 'A';
       for(int i = 0; i < 64; i++)
       {
          LUT[c] = i;
          c++;
       }
    }
    

    Nach den `Z` geht es dann aber leider falsch weiter.

    DeathCubeK schrieb:

    Danach steht in der Deiner LUT:

    LUT['A'] == 0 , LUT['B'] == 1 , LUT['C'] == 2 , und so weiter...

    sollte wohl eher heissen:

    LUT[0] == 'A' , LUT[1] == 'B' , LUT[2] == 'C'



  • 1. jup nach dem Z muss man aufhören und für klein a mit dem richtigen i weitermachen.

    2. Nein das ist richtig LUT['A'] = 0; Damit ich zurück rechnen kann, will ich ja nicht die Bits von A sondern von der Position der Tabelle...



  • leoni_ schrieb:

    1. jup nach dem Z muss man aufhören und für klein a mit dem richtigen i weitermachen.

    Der Beispielcode erhebt keinen Anspruch auf Vollständigkeit, sondern dient lediglich dazu, das Prinzip zu verdeutlichen.

    Ich werde hier nicht den fertigen Code für leoni_'s Hausarbeit schreiben :p

    2. Nein das ist richtig LUT['A'] = 0; Damit ich zurück rechnen kann, will ich ja nicht die Bits von A sondern von der Position der Tabelle...[/quote]

    Du wirst wohl zwei verschiedene Tabellen benötigen. Je eine zum Base64 kodieren und dekodieren 😉


Log in to reply