integer shiften [C]

[xGhost]

Hallo

Ich hab ein 1byte element array.
Nun will ich eine int (32bit / 4byte) in dieses Array moven.
Aber nur die ersten bzw. letzen 3byte.

Nur wie kann ich das "sauber" shiften?
Ich hab so ne pseudo lösung, aber die gefählt mir nicht.

unsigned char *p;
unsigned int digit = '\x00FFFFFF'
unsigned int tmp;

tmp = digit << 16;
*p = tmp >> 8;
++p;

tmp = digit << 24;
*p = tmp >> 8;
++p;

*p = digit >> 8;

Das finde ich nicht gerade sauber,
zumal später nicht genau klar ist, ob nun alle 4byte oder nur 2byte..
dann müsste es fast mit einer while schleife gemacht werden.

Gut "tmp = digit << x" nimmt konstant zu, das könnte man schon
für die while schleiffe nehmen. aber irgendwie finde ich meinen ansatz
scheisse.

Hat jemand ne besser lösung oder idee?

Greets
Ghost

 

[xGhost]

Hab was

unsigned char *p;
unsigned int digit = '\x00FFFFFF'
unsigned int tmp;
int i = 16

do {
  *p = (digit << i) >> 8;
  ++p;
  i += 8;
} while (i < 32)

 

[bsdagent]

Abend

Vieleicht hilf das witer Link

gruss
bsdagent

 

[Vincent Vega]

Ok, nach einigen Malen durchlesen glaube ich zu verstehen, was Du meinst

Also erstmal hast Du ein kleines Verständnisproblem was Shiften betrifft. Der Rechtsshift ist nicht genau definiert, und zwar für den Fall, dass das höchstwertige Bit 1 ist. Betrachte folgenden Pseudocode:

uint16_t val = 0x80; /* = 1000 0000 */

int16_t shifted = val >> 1;

Je nach Compiler und Zahlendarstellung ist das Ergebnis entweder 0x40 (= 0100 000) oder 0xC0 (= 1100 000) oder was anderes.

Um ein einzelnes Byte zuverlässig aus einem Datenwort zu extrahieren, verwende (in C):

uint32_t val = 0x12345678;

uint32_t val34 = (val >> 16) & 0xFF; /* ergibt 0x000000034 */

Damit schiebst Du nach rechts und stellst sicher, dass die links "aufgefüllten" Bits 0 sind. Der Compiler optimiert das weg, wenn er feststellt, dass die &-Verknüpfung unnötig ist. Und falls nicht: Eine &-Verknüpfung kostet nichts. (Es gibt auch andere Wege "richtig" nach rechts zu shiften, aber der hier ist einfach zu vermitteln).

Nun zu Deinem eigenen Problem. Wenn ich Dich richtig verstehe, dann willst Du ein mehrere Bytes breites Datenwort in einem Array ablegen?

uint32_t w = 0x12345678;

/* "Konvertieren in" */

uint8_t a[3] = { 0x12, 0x34, 0x56 };

/* Oder */

uint8_t b[3] = { 0x34, 0x56, 0x78 };

Wenn Du weisst oder sicherstellen kannst, dass a[] bzw. b[] Platz für vier Bytes haben, dann kannst Du einfach schreiben:

a = w & 0xFFFFFF00;
b = (w << 8) & 0xFFFFFF00;

/* viertes Byte einfach ignorieren */

Wenn Du es etwas allgemeiner halten willst, dann kannst Du eine einfache Funktion schreiben. Der von Dir gepostetes Code-Schnipsel löst das Problem ja schon (bis auf die "falsche" Rechtsshifterei). Ich hab mal ein Beispiel angehängt, das ist ein wenig allgemeiner gehalten als Dein Code, kannst ja mal damit rumspielen...

 

[dettus]

weiteres problem was bei dieser pointergeschichte auch noch auftreten kann ist die endianess.

wenn du das also so codest, kann das sein dass es auf deiner pentium/athlonkiste wunderbar rennt.
auf einer sparc aber nicht.

ich wuerde dir daher lieber folgenden code vorschlagen:

unsigned char p;
unsigned int digit=0x00ffffff;
unsigned int tmp;
int i;

tmp=digit;
for (i=0;i<4;i++)
{
  p=tmp&0xff;
  tmp>>=8;
}

oder (wenn du tmp sparen willst...)

unsigned char p;
unsigned int digit=0x00ffffff;
int i;

tmp=digit;
for (i=0;i<4;i++)
{
  p=tmp&0xff;
  digit=((digit>>8)&0x00ffffff)|((digit&0xff)<<24);
}

Der Rechtsshift ist nicht genau definiert, und zwar für den Fall, dass das höchstwertige Bit 1 ist.

da muss ich dir leider widersprechen.
gegeben sei folgender c-code:

unsigned char a=0xc0;
signed char b=0xc0;

printf("a:%4i %4x b:%4i %4x\n",a,a,b,(unsigned char)b);
a>>=1;
b>>=1;
printf("a:%4i %4x b:%4i %4x\n",a,a,b,(unsigned char)b);

ausfuehren ergbit:

a: 192   c0 b: -64   c0
a:  96   60 b: -32   e0

du siehst, dass wenn man einen unsigned datentyp nimmt, das ergebnis nach dem shiften von 0xc0 0x60 ist, bei einem signed datentyp 0xe0.
der grund ist einfach der, dass bei unsigned ein logischer shift stattfindet, bei signed ein arithmetischer: das vorzeichen wird mitgeschoben.
deswegen ist das ergebnis von -64>>1 auch -32.

 

[BrainPain]

[gelöscht]

 

[Vincent Vega]

da muss ich dir leider widersprechen.
gegeben sei folgender c-code:

unsigned char a=0xc0;
signed char b=0xc0;

printf("a:%4i %4x b:%4i %4x\n",a,a,b,(unsigned char)b);
a>>=1;
b>>=1;
printf("a:%4i %4x b:%4i %4x\n",a,a,b,(unsigned char)b);

Du hast natürlich Recht. Dein Beispiel unterstreicht, was ich eigentlich meinte: Man kann nicht davon ausgehen, dass von links her immer mit einer Null aufgefüllt wird (ohne das man sich Gedanken über die Zahledarstellung macht...).

 

[xGhost]

Danke an alle
Sehr Hilfreich.

oder (wenn du tmp sparen willst...)

Geht in meinem fall nicht.
DER (ASN.1) ist litle ending.

Greets

 

[Tron]

weiteres problem was bei dieser pointergeschichte auch noch auftreten kann ist die endianess.

wenn du das also so codest, kann das sein dass es auf deiner pentium/athlonkiste wunderbar rennt.
auf einer sparc aber nicht.

Das ist hier völlig irrelevant.

ich wuerde dir daher lieber folgenden code vorschlagen:

unsigned char p;
unsigned int digit=0x00ffffff;
unsigned int tmp;
int i;

tmp=digit;
for (i=0;i<4;i++)
{
  p=tmp&0xff;
  tmp>>=8;
}

oder (wenn du tmp sparen willst...)

unsigned char p;
unsigned int digit=0x00ffffff;
int i;

tmp=digit;
for (i=0;i<4;i++)
{
  p=tmp&0xff;
  digit=((digit>>8)&0x00ffffff)|((digit&0xff)<<24);
}

Irgendwie kommt mir das alles extrem kompliziert vor, was hier so getrieben wird.

da muss ich dir leider widersprechen.

Und ich dir. Das Resultat von schieben nach rechts bei vorzeichenbehafteten Ganzzahlen ist laut C-Standard implementierungsabhängig. Auf deiner Zweikomplement x86 Kiste hast du zwar ein bestimmtes Ergebnis erhalten, aber das als allgemeingültig hinzustellen ist schlicht falsch.

 

[dettus]

Das Resultat von schieben nach rechts bei vorzeichenbehafteten Ganzzahlen ist laut C-Standard implementierungsabhängig.

ja?
ich sag doch dass es bei vorzeichenlosen zahlen geht?

ich weiss jetzt zwar nicht wo der c-standard liegt, und wo das mit dem rechtsshift steht. aber ich glaube dir.

macht ja auch sinn: rechtsshift soll ja eine moeglichst einefache division durch 2 sein. und weil -64 durch 2 halt =-32 ist sollte das dann da auch rauskommen.
wie der rechner nun intern -64 und -32 darstellt ist sein problem -> implementierungsabhaengig.
also: bei rechtsshift immer unsigned nehmen wenns logisch sein soll

 

[Tron]

ja?
ich sag doch dass es bei vorzeichenlosen zahlen geht?

Du hattest deinem Vorredner widersprochen, der sagte, dass das Ergebnis eines Rechtsschiebens nicht genau definiert ist. Und dieser Widerspruch war schlicht falsch, denn derjenige hatte Recht.

macht ja auch sinn: rechtsshift soll ja eine moeglichst einefache division durch 2 sein. und weil -64 durch 2 halt =-32 ist sollte das dann da auch rauskommen.

WEIT gefehlt. Genau das sagt der Standard nicht. Implementierungsabhängig bezieht sich auf den Wert des Ergebnisses selbst. (Steht in §6.5.7 Absatz 5. Den C-Standard kann man im Netz finden)
Übrigens ist das Linksschieben bei vorzeichenbehafteten Zahlen, die negativ sind, sogar _undefiniert_.

 

[dettus]

junge, gaaanz ruhig.
nicht so aggressiv!
denk auch an deinen blutdruck.

Du hattest deinem Vorredner widersprochen, der sagte, dass das Ergebnis eines Rechtsschiebens nicht genau definiert ist

du denkst immer noch an arithmetische shifts.
vergiss die.
bei dem code braucht man logische.

bits muessen geshiftet werden.
nicht zahlen.

Übrigens ist das Linksschieben bei vorzeichenbehafteten Zahlen, die negativ sind, sogar _undefiniert_.

rotfl.
danke. der witz ist echt gut! fast so schoen wie der "sei epsilon kleiner als 0" *g*
ich musste gerade echt schmunzeln

 

[xGhost]

Ich will jetzt nicht auf das zuvor geschrieben eingehen.

Ich hab das dazu gefunden:

Ist der Datentyp signed, ändert sich das Vorzeichen, wenn eine 1 in die Bitstelle des Vorzeichens gerückt wird. Falls der linke Operand aber einen negativen Wert hat, so ist das Ergebnis Compiler-spezifisch.

Ich hab dazu noch die OpenSSL lib angesehen (asn.1). Soweit
wie ich das gesehen habe, wird einfach ein 2 kompliment gemacht
wenn die Zahl Negative ist, und danach hinausgeschiftet, und später
wieder negiert.

Worum muss ASN.1 nur big endian sein...
Jetzt darf ich für das problem noch ne lösung suchen...

Greets
ghost

// edit //
Ausschnitt aus openssl/crypto/asn1/a_int.c

/* 
 * This converts an ASN1 INTEGER into its content encoding.
 * The internal representation is an ASN1_STRING whose data is a big endian
 * representation of the value, ignoring the sign. The sign is determined by
 * the type: V_ASN1_INTEGER for positive and V_ASN1_NEG_INTEGER for negative. 
 *
 * Positive integers are no problem: they are almost the same as the DER
 * encoding, except if the first byte is >= 0x80 we need to add a zero pad.
 *
 * Negative integers are a bit trickier...
 * The DER representation of negative integers is in 2s complement form.
 * The internal form is converted by complementing each octet and finally 
 * adding one to the result. This can be done less messily with a little trick.
 * If the internal form has trailing zeroes then they will become FF by the
 * complement and 0 by the add one (due to carry) so just copy as many trailing 
 * zeros to the destination as there are in the source. The carry will add one
 * to the last none zero octet: so complement this octet and add one and finally
 * complement any left over until you get to the start of the string.
 *
 * Padding is a little trickier too. If the first bytes is > 0x80 then we pad
 * with 0xff. However if the first byte is 0x80 and one of the following bytes
 * is non-zero we pad with 0xff. The reason for this distinction is that 0x80
 * followed by optional zeros isn't padded.
 */

 

[dettus]

Worum muss ASN.1 nur big endian sein...
Jetzt darf ich für das problem noch ne lösung suchen...

ich weiss jetzt noch immer nicht was LOGISCHES rechts/linksshiften mit big/little endian zu tun haben soll?
das ist nur ein problem wenn man den pointer-weg geht.

Ich hab dazu noch die OpenSSL lib angesehen (asn.1). Soweit
wie ich das gesehen habe, wird einfach ein 2 kompliment gemacht
wenn die Zahl Negative ist, und danach hinausgeschiftet, und später
wieder negiert.

deswegen solltest du dir die shift-variablen auch als unsigned definieren.

ich hab nur gerade gemerkt dass in meinem proggie ohne tmp ein fehler war...
wie dem auch sei...

das hier:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
        unsigned int digit=0x12345678;
        unsigned char p=0;
        int i;

        for (i=0;i<4;i++)
        {
                p=digit&0xff;
                printf("%02X",p);
                digit=((digit>>8)&0x00ffffff)|((digit&0xff)<<24);
        }
        printf("\n");
}

liefert auf einem apple g4 78563412 (also BIIIG endian)
und auf einem amd64 78563412 (also little endian)

ich hoffe dir damit ein wenig weitergeholfen zu haben?

btw: ist die kiste auf der du das machen willst jetzt big oder little endian?

 

[Tron]

junge, gaaanz ruhig.
nicht so aggressiv!
denk auch an deinen blutdruck.

Ich verstehe nicht, was der Kommentar soll.

du denkst immer noch an arithmetische shifts.
vergiss die.
bei dem code braucht man logische.

Ich weiß präzise worum es geht.

bits muessen geshiftet werden.
nicht zahlen.

Was uns der Autor damit sagen will, bleibt mir verschlossen. Bits dienen zur Repräsentation von Zahlen zur Basis zwei.

rotfl.
danke. der witz ist echt gut! fast so schoen wie der "sei epsilon kleiner als 0" *g*
ich musste gerade echt schmunzeln

Da ist kein Witz. Das kannst du im C-Standard exakt nachlesen. Übers linksschieben kann man genau einen Absatz davor nachlesen: §6.5.7 Absatz 4 im ISO C99 Standard (der zuvor verwiesene Absatz 5 bezieht sich aufs rechtsschieben).
Hier das Zitat:

The result of E1 << E2 is E1 left-shifted E2 bit positions; [...] If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Mir erscheint, du weißt nicht recht bescheid.

 

[Tron]

ein 2 kompliment

Das Wort heißt "Zweikompl_e_ment" (Komplement, lat. für Ergänzung). Du willst der Zahl nicht schmeicheln; es ist eine Darstellungsform für Zahlen.

Worum muss ASN.1 nur big endian sein...
Jetzt darf ich für das problem noch ne lösung suchen...

Du hast kein Endianproblem. Du willst doch einfach nur Bits extrahieren. Zudem Hat Zweikomplementdarstellung an sich nichts Big/Little Endian zu tun.

 

[xGhost]

Das Wort heißt "Zweikompl_e_ment" (Komplement, lat. für Ergänzung). Du willst der Zahl nicht schmeicheln; es ist eine Darstellungsform für Zahlen.

unser Tron, korrekt wie immer

Du hast kein Endianproblem. Du willst doch einfach nur Bits extrahieren. Zudem Hat Zweikomplementdarstellung an sich nichts Big/Little Endian zu tun.

Ich schrieb soweit ich denken kann auch nichts in diese Richtung.
Wenn doch, dann tut's mir leid..

Aber ich hab jetzt so ne Lösung im Kopf. Der Post dazu folgt später.

@dettus:
Danke, kann ich in so etwa verwenden, bis auf die Negativen zahlen.
Dazu hab ich aber schon die Idee.
Musste mir schon mühe geben, deinen code richtig zu lesen

Auf deine Frage:
Ich hab nen Intel. Das embedded system[1] ist auch litle endian.

[1] http://de.wikipedia.org/wiki/WRT54G

 

[xGhost]

ich weiss jetzt noch immer nicht was LOGISCHES rechts/linksshiften mit big/little endian zu tun haben soll?

Oops.
Wie man zu Deutsch sagt: "vergä!".
Mein fehler, hatte da etwas falsch im Kopf

 

[dettus]

oh mist, oh mist, oh mist...
ich hab dein originalproggie jetzt endlich geblickt...
ich habs dir falschrum beschrieben.

mist.
okay, also, du hast ein array von char?
daraus willst du ein int machen?
und nicht andersrum?

cool.
dann hast du ein big/little endian problem

aber guck dir einfach mal den code hier an:

int main(void)
{
   signed char p={-1,2,-3,4};
   unsigned int little,big;

   little=(((unsigned char)p[0])<<0)| \
          (((unsigned char)p[1])<<8)| \
          (((unsigned char)p[2])<<16)| \
          (((unsigned char)p[3])<<24);
   big   =(((unsigned char)p[3])<<0)| \
          (((unsigned char)p[2])<<8)| \
          (((unsigned char)p[1])<<16)| \
          (((unsigned char)p[0])<<24);
}

das (unsigned char)p sorgt dafuer dass die shifts logisch werden. und dass die vorzeichen von denen nicht die hoeheren bits im integer ueberschreiben.

 

[xGhost]

Fast.

Das Protokoll ist big endian und der Prozi ist little endian.

Hier ist der Code (er funct )

typedef struct _x509_node
{
    unsigned char *data;
    unsigned char *p;
    unsigned char *end;

    size_t len;
}
x509_node;

static int asn1_add_int(signed int value, x509_node *node)
{
    signed int i = 0, neg = 1;
    unsigned int byte, u_val = 0, tmp_val = 0;

    /* if negate? */
    if (value < 0) {
        neg = -1;
        u_val = ~value;
    } else {
        u_val = value;
    }

    byte = asn1_eval_octet(u_val);

    /* ASN.1 integer is signed! */
    if (byte < 4 and ((u_val >> ((byte -1) * 8)) & 0xFF) == 0x80)
        byte += 1;

    if (x509_realloc_node(node, (size_t) byte + 2) != 0)
        return ERR_X509_MEMORY_ALLOC_FAILED;

    /* tag */
    *(node->p) = ASN1_INTEGER;
    ++node->p;
    
    /* len */
    asn1_add_len(byte, node);

    /* value */
    for (i = byte; i > 0; --i) {

        tmp_val = (u_val >> ((i - 1) * 8)) & 0xFF;
        if (neg == 1)
            *(node->p) = tmp_val;
        else
            *(node->p) = ~tmp_val;

        if (i > 1)
          ++node->p;
    }

    if (node->p != node->end)
        return ERR_X509_POINT_ERROR;

    return 0;
}