C++ String mit hexadezimaler Repräsentation einer Zahl in einen Integer umwandeln (Was tut der Code?)

[Vulpecula]

Guten Abend zusammen!

Ich bin heute auf ein Codefragment gestoßen, das mir Kopfzerbrechen bereitet. Es handelt sich hier (angeblich) um eine Möglichkeit, einen String, der die hexadezimale Repräsentation einer Zahl enthält, in einen Integer (hier vom Typ Long) umzuwandeln:

static const long hextable[] =
{
   [0 ... 255] = -1,                     // bit aligned access into this table is considerably
   ['0'] = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, // faster for most modern processors,
   ['A'] = 10, 11, 12, 13, 14, 15,       // for the space conscious, reduce to
   ['a'] = 10, 11, 12, 13, 14, 15        // signed char.
};

/**
* @brief convert a hexidecimal string to a signed long
* will not produce or process negative numbers except
* to signal error.
*
* @param hex without decoration, case insensitive.
*
* @return -1 on error, or result (max (sizeof(long)*8)-1 bits)
*/
long hexdec(unsigned const char *hex)
{
  long ret = 0;
  while (*hex && ret >= 0)
  {
    ret = (ret << 4) | hextable[*hex++];
  }
  return ret;
}

Im Prinzip ist der Code für mich wertlos, da er keine negativen Werte abbilden kann, aber trotzdem möchte ich gerne wissen, was da vor sich geht.

Etwas konkreter: Ich könnte schon verstehen, was in der while-Schleife passiert (eine bitweise Operation), nur störe ich mich an dem hextable[] Konstrukt, denn sowas habe ich (in meiner zugegeben kurzen Zeit mit C++) bisher noch nicht gesehen. Es sieht zunächst nach einem Array aus, ist dann aber doch keins. Wie nennt man sowas?

Leider hatte ich noch keine Zeit, den Code zu kompilieren und auf einem AVR hochzuladen, aber vielleicht mag mir ja jemand auf die Sprünge helfen und/oder mir sagen, wonach ich auf der allwissenden Müllhalde suchen muss, um mehr zu erfahren.

Vielen Dank,
Vulpecula

 

[michi.o]

hextable ist ein Array. Die Art wie das deklariert wurde ist mir neu und anscheinend auch nicht Standardkonform. Auf der StackOverflow Seite, die Du verlinkt hast, ist nochmal das volle Array für normale Compiler zu sehen.

Im Prinzip heißt das:

• Initialisiere Position 0 bis 255 mit -1. Initialisiere Position '0'
• Initialisiere Position '0' (=48) mit 0 und die darauffolgenden Positionen mit 1,2,3 usw.
• Initialisiere Position 'A' (=65) mit 10 und die darauffolgenden Positionen mit 11,12,23, usw
• Dasselbe nochmal mit 'a' (=141)

So macht das auch Sinn. Die while Schleife zeigt mit *hex auf den String. *hex ist am Ende vom String 0 und beendet somit die while schleife. Mit *hex++ wird hex immer eine Position weiter gesetzt. Die zweite Bedingung ret>=0 ist dafür da, dass die Schleife abbricht wenn auf eine -1 in dem LookUp Array zugegriffen wurde.

Als letztes bleibt noch der Inhalt von while:
hextable[*hex++] holt sich Anhand des ASCII Werts die entsprechende Zahl aus dem LookUp Array. Diese Zahl ist maximal 4 Bit groß. Durch den | Operator wird die Zahl dazu addiert.
(ret << 4) schiebt das Ergebnis vom letzten Durchlauf um 4 Bit weiter, so dass die nächste Zahl in den unteren 4 Bit landen kann.

Ziemlich netter und schneller Code.

Im Prinzip ist der Code für mich wertlos, da er keine negativen Werte abbilden kann

Hex Strings bilden nie direkt negative Werte ab. Das sind einfach nur Bits. Das negative Vorzeichen kommt vom Datentyp. 0xFF kann 255 sein oder -1 (bei einer 8 Bit Variablen).

 

[randomfile]

hextable ist ein Array, das speziell initialisiert wird: designated initializers.

Zuerst werden alle Einträge von Indexposition 0 bis 255 auf -1 gesetzt, also hextable[0]=-1.... Die Angabe ['0'] entspricht im Array der Position 48 (=dezimal wert des ASCII Zeichens '0') und die darauf folgenden Indizes werden einsprechend hochgezählt und mit den rechts stehenden Werten belegt: D.h. die Angabe von ['0'] = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 bewirkt hextable[48]=0, hextable[49]=1, ... , hextable[57]=9. vgl. mit einer ASCII Tabelle. Analog steht ['A'] = 10, 11, 12, 13, 14, 15 für hextable[65]=10, ..., hextable[70]=15....

Ergänzung (7. Dezember 2018)

Designated initializers gibt es seit C99 Standard: https://www.ibm.com/support/knowledgecenter/en/ssw_ibm_i_72/rzarg/designators.htm

Ergänzung (7. Dezember 2018)

Bzw. auch hier Infos dazu: https://en.cppreference.com/w/c/language/array_initialization

 

[Vulpecula]

So, über die Feiertage habe ich tatsächlich mal ein wenig Zeit, mich damit auseinanderzusetzen. Erstmal vielen Dank an @michi.o und @randomfile für die Erklärungen. Auf die "Designated Initializers" wäre ich tatsächlich nicht gekommen.

So langsam erschließt sich mir auch das Konzept dahinter. Das Ganze scheint aber nur deswegen zu funktionieren, weil der Char (z.B. das ['A'] beim Initialisieren) im Datentyp Long genau durch die Zahl repräsentiert wird, der seiner Position in einer standard ASCII Tabelle entspricht; so wie @randomfile es erläutert hat.

Ich frage mich nur, was sein Kommentar ("will not produce or process negative numbers except to signal error") zu bedeuten hat. Denn wie @michi.o schon richtig angedeutet hat, ist es doch abhängig von dem Datentyp in den konvertiert wird. Seine Funktion hexdec() hat ja immerhin einen Signed Long als Rückgabetyp. Soll heißen: Ein 0xFFFFFFFF sollte bei diesem Datentyp dezimal als -1 repräsentiert werden.

Nungut... Ich denke, ich werde nachher mal ein paar Versuche auf einem Arduino machen, um das ganze noch besser zu verstehen.

Grüße,
Vulpecula

 

[nullPtr]

@michi.o hat übrigens recht, das ist kein valider C++-Code (C++20 wird das auch supporten). Allerdings sehr wohl C. Diese "[0]" in der Array-Initialisierung sind Designators (C99, §6.7.9).

 

[FranzvonAssisi]

Er schreibt doch unten drunter

> @return -1 on error,

...

= akzeptiert und verarbeitet keine negativen Zahlen außer um einen Fehler anzuzeigen.

In Englisxh:

"will not produce or process negative numbers except to signal error"

Lg

 

[Vulpecula]

Ja, die Funktion liefert -1 bei einem Fehler. Allerdings wird das nur dann passieren, wenn man irgendetwas anderes als 0-9 bzw. A-F an die Funktion übergibt. Sprich: Wenn man keine Hex-Zahl übergibt.

Und ja, mir ist klar, was sein Kommentar auf deutsch heißt. Aber wenn ich @michi.o zitieren darf:

Hex Strings bilden nie direkt negative Werte ab. Das sind einfach nur Bits. Das negative Vorzeichen kommt vom Datentyp. 0xFF kann 255 sein oder -1 (bei einer 8 Bit Variablen).

Es kommt nicht darauf an, was ich da "reinwerfe", sondern was bezüglich der Zieldatentyps daraus gemacht wird.

Ein kleines Beispiel: Wenn ich 0xFFFFFFFE an die oben stehende Funktion übergebe, wo der Zieldatentyp ein Long (a.k.a. int32_t) ist, dann ist es in Dezimalrepräsentation eine -2. Würde man als Rückgabedatentyp allerdings einen Unsigned Long (a.k.a. uint32_t) wählen, dann wäre das Ergebnis von 0xFFFFFFFE in Dezimalrepräsentation 4294967294.

Und genau deshalb verstehe ich nicht, warum er behauptet, seine Funktion könne keine negativen Zahlen 'produzieren' und/oder 'verarbeiten'.

Ergänzung (26. Dezember 2018)

Kleine Ergänzung: Ich habe es gerade mal ausprobiert. Habe die Funktion dahingehend angepasst, dass sie einmal einen int32_t und einmal einen uint32_t zurückgibt. Das Ergebnis ist wie erwartet. Umso mehr wundere ich mich über den Kommentar im Code. Aber gut - es funktioniert und das anscheinend ziemlich schnell und das gefällt.

P.S.: Der Compiler, der mit der Arduino IDE kommt (avr-gcc) mag die oben angeführte Deklaration übrigens nicht. Stattdessen habe ich die Alternative benutzt, die weiter unten auf der Stackoverflow Seite zu finden ist.

 

[FranzvonAssisi]

Weil du ja einfach "missbraucht" das der Code nicht testet ob er aufs Sign Bit shiftet, oder?

Ja, letztendlich hast du recht, weil du den Bits / Zeichen immer eine eigene Bedeutung zuschreiben kannst.

Es ist aber was ganz anderes, als eine reine Konvertierung von Base 16 zu Base 10 / Base 2! Du benutzt halt einfach das Design des Algorithmus, um die Bedeutung komplett zu verändern.

Es ist einfach ein Fakt, dass [0xFFFFFFFE in Base 16] [4294967294 in Base 10] sind. (Klammern um Zugehörigkeit einfacher erkennbar zu machen)

Wenn du das dann einfach als was anderes ausgibst - klar können dann da auch negative Werte entstehen...

Ich bin gerade nur am Handy und wegen 10 Stunden Zeitverschiebung müde, insofern kann es sein, dass das gar nicht stimmt, aber ich bin da eigentlich ganz zuversichtlich...

 

[michi.o]

Und genau deshalb verstehe ich nicht, warum er behauptet, seine Funktion könne keine negativen Zahlen 'produzieren' und/oder 'verarbeiten'.

Ich denke Du hast den Kommentar falsch verstanden. Er meint nur, dass diese Funktion niemals eine negative Zahl zurückgeben wird, außer bei einem Fehler. D.h. so lange kein Fehler erzeugt wird, wird diese Funktion immer positive Zahlen vom Typ long ausgeben.
Negative Zahlen gehen schon, wenn das Ergebnis auf den Zieldatentyp gecasted wird und dieser weniger Bits hat. Das hier geht ja z.B. auch:

long x = 0xFFFFFFFF;
int y = (int)x; // = -1

OK, im Fall der 64 Bit Zahl -1 könnte er unrecht haben. Da müsste bei ‭0xFFFFFFFFFFFFFFFF‬ eigentlich -1 rauskommen. Ist halt ne Begrenzung vom verwendeten Rückgabe Datentyp.

 

[BlackMark]

Diese Lookup Lösung ist zwar sehr schnell, aber auf einem Microcontroller würde ich das nicht machen. Du verschwendest mit dem Lookup-Table 256 * sizeof(long) = 256 * 4 = 1024 = 1kB RAM. Auf einem Arduino Uno hast du 2kB RAM und davon geht die Hälfte für diesen Lookup-Table drauf, das lohnt sich einfach überhaupt nicht.
Man könnte den Lookup-Table statt im RAM auch im Flash speichern, braucht dann aber mehr Clock Cycles für den Lookup und so viel Flash hat man meistens auch nicht zur Verfügung.

Außerdem, wenn der Lookup zur Compilezeit passieren kann, kann man sich eine constexpr Funktion schreiben, das ist dann sogar nochmal schneller als die Lösung mit Lookup-Table und hat absolut keinen Runtime-Overhead.

Gruß
BlackMark

 

[Vulpecula]

Frohes neues Jahr zusammen!

Also, erstmal vielen Dank für die zahlreichen konstruktiven Beiträge. Und ja, @FranzvonAssisi und @michi.o haben natürlich recht. Eine Konvertierung von Base 2 zu Base 16 hat erstmal nichts mit dem Datentyp zu tun, auf den ich Caste - das ist nur eine Eigenschaft, die ich ausnutze.

Vielen Dank auch an @BlackMark für den Hinweis. Ja, die Lookup-Table verbraucht viel RAM, wäre in diesem Fall aber durchaus zu verschmerzen. Der 328p ist hier nur dafür da, Daten zu empfangen (via CAN Bus, deswegen auch die HEX-DEC Geschichte) und via Serial Port (USB) weiterzureichen. Allerdings erscheint es mir als die sinnvollere Alternative, die Daten direkt im HEX-Format weiterzureichen und von meiner Software zurückwandeln zu lassen. Die Software wird auf einem x86-System (alá NUC oder ähnlich) laufen, wo deutlich mehr Ressourcen zur Verfügung stehen.

Grüße - Vulpecula

 

[BlackMark]

Warum bekommst du von einem CAN Bus ASCII-encoded hex values? Solltest du nicht einfach raw data (uint8_t array) bekommen? Verwendest du irgend eine fertige Library, die dir die Daten als String zurück gibt?
Wahrscheinlich machst du jetzt folgendes: CAN bus -> raw data -> hex string -> raw data -> decimal string -> serial port
Ich würde Vorschlagen, du machst: CAN bus -> raw data -> decimal string -> serial port
Oder noch besser, wenn du post-processing am x86-System machst: CAN bus -> raw data -> serial port

Gruß
BlackMark

 

[Vulpecula]

@BlackMark: Ich habe gerade nicht viel Zeit, deswegen erstmal eine kurze Antwort: Ich benutze die Seeed Studio CAN Bus Shield Library. Da werden die zu sendenden bzw. zu empfangenden Daten in ein unsigned char Array geschmissen bzw. daraus gelesen. Das ist, wenn ich mich nicht irre, ein uint8_t. Die Ursprungsdaten sind Integerwerte, die ich durch bytewise shifting in das zu sendende Array bekomme.

 

[BlackMark]

Ja dann ist doch ideal. Nimm das Array und schreib es, genau so wie es ist, über Serial raus. Auswerten kannst du dann dort, wo du viel mehr Rechenleistung und Ressourcen hast.

Gruß
BlackMark