[Dark_Tengulist]

Folgendes: Ich muss eine bestimmte Bitfolge seriell "über Funk" übertragen. Im Rahmen einer Kollisionsbehandlung, die vom Hersteller vorgegeben ist. Ich bekomme eine Nummer von einem Device zugeschickt. Wenn mehrere Devices durcheinander senden, muss ich eine Sequenz senden aus Position der Kollision (5 bit), die bis dahin gelesene Nummer (plus 1 oder 0 an der Kollisionsposition) und nen 8-bit CRC. Mein Testcase sieht jetzt so aus, dass an Position 6 eine Kollision auftritt. Die Nummer vom Device ist 000010011usw. Ich kann 00001 sauber lesen und danach kommt die Kollision. Also muss ich "00110000010" plus crc senden.
Im Handbuch steht: Generatorpolynom ist x^8+x^4+x^3+x^2+1 = 0x1D und pre-set-value ist 0xFF. bitreihenfolge ist msb...lsb
Und jetzt geht der ganze Spaß nämlich los. Es ist ein Beispielcode dabei:

Spoiler:(zum lesen bitte Text markieren)

#include <stdio.h>
#define CRC_PRESET 0xFF
#define CRC_POLYNOM 0x1D
void calc_crc(unsigned char * crc,
unsigned char data,
unsigned char Bitcount)
{
     *crc ^= data;
     // crc = crc (exor) data
     do
     {
          if( *crc & 0x80 )
          // if (MSB-CRC == 1)
          {
               *crc<<=1;
               // CRC = CRC Bit-shift left
               *crc ^= CRC_POLYNOM;
               // CRC = CRC (exor) CRC_POLYNOM
          }
          else
          {
               *crc<<=1;
               // CRC = CRC Bit-shift left
          }
          printf("CRC: %02X ", *crc);
     } while(--Bitcount);
     printf("\n");
}
// output result step by step


void main(void)
{
     const cmd=0x00;
     /* 5 Bit command, aligned to MSB */
     const ident[4]={0x2C, 0x68, 0x0D, 0xB4 };
     unsigned char crc;
     int i;
     crc = CRC_PRESET;
     /* initialize crc algorithm */
     calc_crc(&crc, cmd, 5); /* compute 5 crc Bits only */
     for(i=0; i<4; i++)
          calc_crc(&crc, ident[i], 8);
          /* crc = 0x9E at this point */
     printf("%02X\n",crc);
     getch();
}

Jetzt bin ich mir nicht sicher, ob ich meine Bitfolge komplett in diese Funktion reingeben soll, oder erst nur die ersten 5 Bit und dann die 6 Bit oder wie auch immer. Aber egal, was ich auch mache, ich komme mit diesem Programm nicht auf das selbe Ergebnis wie mit diesem Onlinerechner, den ich mir zur Verifizierung mal angeschaut habe: http://www.zorc.breitbandkatze.de/crc.html
Da hab ich auch schon sämtliche Optionen durchprobiert. Die meisten Lösungen habe ich auch schon an meiner Sendeeinheit ausprobiert, aber erfolglos. Vom Device kommt nichts zurück. Ich bin jetzt kurz davor, einfach diese letzten 8 Bit zu bruteforcen um mir dann irgendeinen Algorithmus zu basteln, der mir dann das ergebnis berechnet. Vorher möchte ich aber hier nochmal nachfragen, ob jemand ne Idee hat.

[jabu]

Der Algorithmus macht einen guten Eindruck, wenngleich ich mich nicht dafür verbürgen kann. Der hat anscheinend in folgender Zeile eine Optimierung für Speed und Speicher, welche kleinen µCs zugute kommen dürfte:

*crc ^= data;

Damit ist etwas aus der Loop wegoptimiert. Du kannst Code u. Werte z.B. hiermit checken, aber alles ohne Gewähr:

Spoiler:(zum lesen bitte Text markieren)

#include <stdio.h>

#define N(a) (sizeof(a)/sizeof(a[0]))
#define CRC_PRESET  0xFF
#define CRC_POLYNOM 0x1D

typedef unsigned char uchar;

const uchar data[] = {       1, 0,1,1,1,   /* 0x17 */
                       0,0,1,0, 1,1,0,0,   /* 0x2C */
                       0,1,1,0, 1,0,0,0,   /* 0x68 */
                       0,0,0,0, 1,1,0,1,   /* 0x0D */
                       1,0,1,1, 0,1,0,0 }; /* 0xB4 */

int main(void)
{
    int i;
    uchar crc = CRC_PRESET;

    for (i = 0; i < N(data); ++i)
    {
        if (((crc & 0x80) ? 1 : 0) != data[i])
            crc = (crc << 1) ^ CRC_POLYNOM;
        else
            crc <<= 1;
    }

    printf("0x%02X\n", crc);
    return 0;
}

Anscheinend gibt es zumindest bei CRC8 Probleme mit dem CRC-Tool unter deinem Link, dieses funktioniert bei mir:
http://depa.usst.edu.cn/chenjq/www2/...alculation.htm
Allerdings müsstest du dafür in deinem Code testweise CRC_PRESET auf 0x00 setzen, denn 0xFF wird nicht unterstützt.

Zu deiner Frage, ob nach 5 Bit + Rest aufgeteilt werden sollte: Das ist eigentlich egal, wenn man es richtig macht, denn der Algorithmus arbeitet sich immer ab dem MSB in Richtung LSB ab. Bei 5 Bit hättest du aber 8-5=3 schädliche führende Nullen. Also benötigst du bei deinem Code ein Left Shift um diese drei Stellen, hier exemplarisch anhand des Hex-Wertes 0x17:

const cmd = 0x17 << (8-5);

Den Rest kannst du einfach anhängen, sofern am MSB ausgerichtet und die Zahl der Schleifendurchläufe an die der Bits angepasst ist. Es verhält sich dann etwa so, als hättest du einen kontinuierlichen Bitstrom, indem immer nur die benötigten Bits abgearbeitet werden, beginnend am MSB.
Der Code im Spoiler liefert dasselbe, ist aber eben nicht in der Weise optimiert, weshalb man ihn leichter durchschauen kann. Die Hexwerte aus dem Code vom "Handbuch" liegen dort in data[] in Form von einzelnen Bits vor, wobei je Bit gleich ein Byte vereinnahmt wird. Durch Vergleich sieht man die Cleverness der Optimierung in deinem Beispiel. Bei Problemen kann es jedoch hilfreich sein, sich des Bitmusters zu vergewissern und anhand idiotensicheren Codes gegenzuchecken.

[Dark_Tengulist]

Ok, danke. Das mit den führenden Nullen könnte tatsächlich das Problem gewesen sein, warum das nicht funktioniert hat.

Was ich jetzt noch nicht ganz blicke ist, warum bei "meinem" Code zuerst noch 5 nullen durch die crc-funktion geschoben werden. Hat das irgendeine tiefere Bedeutung?

Ich werde dann morgen mal deinen Code ausprobieren und gucken, ob es endlich funktioniert

[jabu]

Habe gerade leider wenig Zeit, also nur kurz: Führende Nullen sind immer dann ein Problem, wenn sie nicht Bestandteil des Codes sind, also Zusatzbits bewirken würden. In meinem letzten Beitrag habe ich die Zeile aufgeführt, die du in deinem Code für deine 5 Bit manipulieren musst, ist selbsterklärend. Das ist der Wert cmd, wo du die Nullen drin hattest, siehe auch den Kommentar in deinem Code unter der Zeile.
Durch das Left Shift um (8-5) Stellen sind die führenden Nullen weg, dafür hast du folgende Nullen. Die sind allem Anschein nach aber neutral, solange die Schleife nur (8-nCmd) nCmd-mal durchlaufen wird, wobei nCmd der Anzahl deiner cmd-Bits entspricht, hier also 5. Also kannst du eine Variable nCmd einführen:

const cmd = 0x17 << (8-nCmd);
calc_crc(&crc, cmd, nCmd);

Diese^ zwei Zeilen wirst du ja in deinem Code wiederfinden. Die Bitfolge aus 0x17 ist nur ein Beispielwert für deine nCmd=5 Anfangsbits, welche ich sowohl in deinen als auch in meinen Code eingesetzt habe, um dir die Entsprechung zu zeigen. Die 0x17 ist also deine ursprüngliche Bitfolge, welche hier exemplarisch verwendet wird und selbst keine führenden Nullen enthält. Solltest du führende Nullen in der Bitfolge haben, ist das kein Problem, denn nCmd legt ja fest, wieviele Bits berücksichtigt werden. Am besten legst du mal beide Programme nebeneinander, denn auch alle anderen Werte aus deinem Programm findest du entsprechend in meinem Programm. Mein Programm ist nicht für µCs optimiert, sondern für Übersichtlichkeit, damit du siehst, was mit den einzelnen Bits geschieht, um diese testweise modifizieren zu können. Es soll das Verständnis schulen, ist also nicht produktiv gedacht. Alles, was du mit deinem Programm testest, kannst du daher mit meinem gegenprüfen bzw. für beide einen Test schreiben.
Bei deinem Code ist wichtig, dass nach dem Left Shift die resultierenden Folgenullen am LSB nicht mit Müll gefüllt sind. Hier rücken automatisch Nullen nach, was funktioniert. Aber manipuliertest du eine der Folgenullen, hätte der Algorithmus ein Problem. Normalerwise macht man das ja nicht. Aber ich kann nicht wissen, wie du später deine Bitmuster generierst, daher dieser Hinweis.

[Dark_Tengulist]

Ich glaube, wir haben ein wenig an einander vorbei geredet. Oder ich hab jetzt nicht ganz verstanden, was du mir sagen wolltest

Ich will ja gar keine Nullen haben, die ich dann wegschieben muss. Ich meinte nur, dass das Problem, weshalb mein Beispielcode falsche Ergebnisse geliefert hat, war, dass ich ihn falsch benutzt habe, weil er mit meinen Daten dann nicht richtig umgehen konnte, eben wegen dieser doofen Nullen.

Was ich dann meinte ist, dass in meinem Beispielmain ja noch 5 Nullen aus cmd in die crc-funktion geschoben werden, weshalb sich der wert hinter crc ja verändert (gegenüber dem preset) bevor mein array mit den nutzdaten kommt. Ich war mir jetzt nicht sicher, ob das einfach nur ein Beispiel ("Hey, du brauchst das zwar nicht, aber schau, sowas kann man auch machen") ist, oder mein System hier tatsächlich so eine Initialisierung braucht. Das hat mich etwas stutzig gemacht. Aber offensichtlich braucht es das nicht, denn ich habe jetzt mal deinen code durchlaufen lassen (es kommt 0x3e raus) und gesendet und es kam direkt die richtige Antwort zurück.
Die Daten liegen hier eh als einzelne bits in nem integer-array rum, von daher kann ich das auch besser so machen. der µC hier ist eh total überdimensioniert

Vielen Dank nochmal