[c] converteren (grote)hex buffer naar decimaal (ascii)

[Verwijderd]

Hallo mensen,
Ik zit met het probleem dat ik een vrij grote hex buffer moet converteren (10 bytes) naar een decimale (ascii) representatie.

Normaal gesproken zou ik de data gewoon in een unsigned long long stoppen en daarna de decimale ascii representatie uitrekenen.
Maar aangezien een lon long 8 bytes is kom ik hier niet meer mee uit de voeten.

Heeft er iemand misschien een idee hoe ik dit het beste zou kunnen oplossen?

[HuHu]

Ondersteund je compiler een octaword of double quadword? Die zijn 128 bits.

[farlane]

Geef eens een voorbeeld want het is me niet helemaal duidelijk wat je met 'hex buffer' bedoeld.

[Verwijderd]

Ik werk op een m68k (coldfire)
Dit is een 32 bitter

ter verduidelijking van wat ik wil bereiken
bijv een buffer gevult met de waarden {0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff} (10 bytes)
zou als uitkomst deze decimale "1208925819614629174706175" representatie hebben.

[FragFrog]

HuHu schreef op vrijdag 25 juni 2010 @ 09:10:
Ondersteund je compiler een octaword of double quadword? Die zijn 128 bits.

Met hem

Al zou je wellicht ook drie ints kunnen gebruiken na wat shiften (of een int64 en een normale int). 80 bits in een normaal datatype wordt lastig gok ik.

[matthijsln]

Verwijderd schreef op vrijdag 25 juni 2010 @ 09:30:
Ik werk op een m68k (coldfire)
Dit is een 32 bitter

ter verduidelijking van wat ik wil bereiken
bijv een buffer gevult met de waarden {0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff} (10 bytes)
zou als uitkomst deze decimale "1208925819614629174706175" representatie hebben.

Je hebt gewoon een buffer dus Dat je hier voor hex kiest als representatie maakt natuurlijk niks uit voor de waardes in de buffer.

Indien het mogelijk is zou je http://gmplib.org/ kunnen gebruiken. Kan je die lib niet gebruiken zul je zelf wat arbitrary precision math functies moeten maken om een itoa() te maken voor integers die groter zijn dan de built-in types.

[Verwijderd]

Ik ga ff kijken of ik die gmplib draaiend krijg op mijn platform

Ik heb net trouwens wel een stukje code geschreven die het aan kan (zeer inefficient)
maar toch even delen met de rest.

C:

#include <string.h>
#include <stdio.h>

void addBuffers(char* buf1,char*buf2,int size){
    unsigned int carry=0;
    int x;
    for(x=(size-1);x>=0;x--){
        buf1[x]+=buf2[x]+carry;
        carry=buf1[x]/10;
        buf1[x]=(buf1[x]%10);
    }
}

int main(int argc,char ** argv){
    unsigned char confData[]={0x55,0x65,0xff,0xff,0x87,0x34,0xab,0xdd,0xbb,0xff};//403282718806623532203007
    //unsigned char confData[]={0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff};//18446744073709551615

    char store[30];
    char adder[30];
    int x,y;
    unsigned char tester;

    memset(store,0,sizeof(store));
    memset(adder,0,sizeof(adder));
    adder[sizeof(adder)-1]=1;
    for(x=sizeof(confData)-1;x>=0;x--){
        tester=confData[x];
        printf("parsing byte %d > %x\n",x,tester);
        for(y=0;y<8;y++){
            if(tester&(1<<y))addBuffers(store,adder,sizeof(store));
            addBuffers(adder,adder,sizeof(adder));
        }
    }
    printf("result:\n");
    for(x=0;x<sizeof(store);x++)printf("%c",store[x]+'0');
    printf("\n");
    return 0;
}

verder ben ik nu de gmp lib aan t doorspitten.

Heb wel een functie gevonden die mijn probleem in 1 keer oplost:

Function: char * mpz_get_str (char *str, int base, mpz_t op)

Convert op to a string of digits in base base. The base argument may vary from 2 to 62 or from −2 to −36.

For base in the range 2..36, digits and lower-case letters are used; for −2..−36, digits and upper-case letters are used; for 37..62, digits, upper-case letters, and lower-case letters (in that significance order) are used.

If str is NULL, the result string is allocated using the current allocation function (see Custom Allocation). The block will be strlen(str)+1 bytes, that being exactly enough for the string and null-terminator.

If str is not NULL, it should point to a block of storage large enough for the result, that being mpz_sizeinbase (op, base) + 2. The two extra bytes are for a possible minus sign, and the null-terminator.

A pointer to the result string is returned, being either the allocated block, or the given str.

[ Voor 94% gewijzigd door Verwijderd op 25-06-2010 11:06 ]

[Soultaker]

Zo inefficient is die code niet hoor. Voor de context van je probleem (enkele tientallen cijfers converteren) lijkt me het sowieso een prima oplossing.

Ik zou het er dus gewoon bij laten, tenzij je nog veel meer met grote getallen wil gaan rekenen in dit programma, dan is een library als GMP natuurlijk wel nuttig.

[ Voor 35% gewijzigd door Soultaker op 25-06-2010 15:45 ]

[.oisyn]

Soultaker schreef op vrijdag 25 juni 2010 @ 14:59:
Zo inefficient is die code niet hoor.

Nou, hij zou de divisions en modulos nog weg kunnen werken

[Soultaker]

Ja klopt, maar dat is toch een beetje gerommel in de marge ben ik bang. (Sowieso is dat een trade-off tussen een deling en branching; geen idee hoe zich dat verhoudt tegenwoordig, maar branch mispredictions zijn duur en rekenkundige operaties niet meer zo kostbaar als vroeger.)

[DexterDee]

Soultaker schreef op vrijdag 25 juni 2010 @ 19:55:
Ja klopt, maar dat is toch een beetje gerommel in de marge ben ik bang. (Sowieso is dat een trade-off tussen een deling en branching; geen idee hoe zich dat verhoudt tegenwoordig, maar branch mispredictions zijn duur en rekenkundige operaties niet meer zo kostbaar als vroeger.)

Tja, de juiste context om dat te kunnen beoordelen hebben we niet. Als die code eens per tien minuten uitgevoerd wordt zou ik zeggen, die voorbeeldcode is meer dan prima. Maar moet die conversie honderd keer per seconde uitgevoerd worden, dan is nadenken over optimalisatie geen overbodige luxe

[.oisyn]

Soultaker schreef op vrijdag 25 juni 2010 @ 19:55:
(Sowieso is dat een trade-off tussen een deling en branching; geen idee hoe zich dat verhoudt tegenwoordig, maar branch mispredictions zijn duur en rekenkundige operaties niet meer zo kostbaar als vroeger.)

cmovcc en setcc. Geen branching voor nodig . En delingen zijn nog altijd duur, en branchprediction is best goed.

[ Voor 141% gewijzigd door .oisyn op 26-06-2010 00:49 ]

[.oisyn]

net even getest

C++:

#include <iostream>
#include <cstdlib>
#include <intrin.h>

void addbuf1(char * pDest, const char * pSrc1, const char * pSrc2, int len)
{
    char carry = 0;

    for (int i = 0; i < len; i++)
    {
        char c = pSrc1[i] + pSrc2[i] + carry;
        carry = c / 10;
        pDest[i] = c % 10;
    }
}

void addbuf2(char * pDest, const char * pSrc1, const char * pSrc2, int len)
{
    char carry = 0;

    for (int i = 0; i < len; i++)
    {
        char c = pSrc1[i] + pSrc2[i] + carry;
        if (c >= 10)
        {
            c -= 10;
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        pDest[i] = c;
    }
}

int result(const char * pBuf, int len)
{
    int c = 0;
    for (int i = 0; i < len; i++)
        c += pBuf[i];
    return c;
}


int wmain()
{
    const int cBufSize = 1024;
    char buf1[cBufSize], buf2[cBufSize], dest[cBufSize];
    for (int i = 0; i < cBufSize; i++)
    {
        buf1[i] = rand() % 10;
        buf2[i] = rand() % 10;
    }

    for (int i = 0; i < 10; i++)
    {
        int t = -(int)__rdtsc();
        addbuf1(dest, buf1, buf2, cBufSize);
        t += (int)__rdtsc();
        std::cout << "div: " << t << " - " << result(dest, cBufSize) << std::endl;

        t = -(int)__rdtsc();
        addbuf2(dest, buf1, buf2, cBufSize);
        t += (int)__rdtsc();
        std::cout << "if:  " << t << " - " << result(dest, cBufSize) << std::endl;
    }

}

div: 21616 - 4688
if:  14784 - 4688
div: 21272 - 4688
if:  12000 - 4688
div: 21272 - 4688
if:  14800 - 4688
div: 21272 - 4688
if:  13776 - 4688
div: 21272 - 4688
if:  14096 - 4688
div: 21296 - 4688
if:  12008 - 4688
div: 21248 - 4688
if:  11536 - 4688
div: 21240 - 4688
if:  11496 - 4688
div: 21248 - 4688
if:  11504 - 4688
div: 21264 - 4688
if:  11696 - 4688

MSVC++ genereert helaas nooit CMOV instructies, maar met branching is de code dus alsnog bijna 2x zo snel.


.edit: met CMOV implementatie erbij

C++:

void addbuf3(char * pDest, const char * pSrc1, const char * pSrc2, int len)
{
    char carry = 0;
    int ten = 10;

    for (int i = 0; i < len; i++)
    {
        char c = pSrc1[i] + pSrc2[i] + carry;
        __asm {
            xor eax, eax
            cmp c, 10
            cmovge eax, ten
            setge carry
            sub c, al
        }
        pDest[i] = c;
    }
}

div: 21632 - 4688
if:  15272 - 4688
cmov:13936 - 4688
---
div: 21272 - 4688
if:  12344 - 4688
cmov:13912 - 4688
---
div: 21272 - 4688
if:  14792 - 4688
cmov:13936 - 4688
---
div: 21520 - 4688
if:  14568 - 4688
cmov:14056 - 4688
---
div: 21328 - 4688
if:  14784 - 4688
cmov:13904 - 4688
---
div: 21272 - 4688
if:  14488 - 4688
cmov:13936 - 4688
---
div: 21464 - 4688
if:  14792 - 4688
cmov:13864 - 4688
---
div: 21288 - 4688
if:  12576 - 4688
cmov:13888 - 4688
---
div: 21272 - 4688
if:  12264 - 4688
cmov:13864 - 4688
---
div: 21264 - 4688
if:  15008 - 4688
cmov:13880 - 4688

Scheelt dus niet zo heel veel.

.edit3: grappig trouwens dat de if versie ook wat duurder is geworden. Waarschijnlijk doet de branch predictor z'n werk minder goed nu er wat meer code is.

.edit4: overigens is er ook nog de hele oude AAM instructie die nooit iemand gebruikt. Die deelt AL door 10 en zet het resultaat in AH en de rest in AL, precies wat de TS wil. Maar die instructie is zo unoptimized als de pest en is nog een stuk langzamer dan een IDIV op een 32 bits register (ik kom daarmee op zo'n 27000 cycles voor een functie die gebruik maakt van AAM)

[ Voor 29% gewijzigd door .oisyn op 26-06-2010 01:15 ]

[Soultaker]

Echter op een ander OS (64-bit Linux 2.6.34) met een andere processor (AMD Athlon64) en een andere compiler (GCC 4.4.4) komt de vergelijking andersom (in het voordeel van de deling) uit.

g++ -O2 -m32	g++ 4.4.4 -O2 -m64
div: 11993 - 4529 if: 12768 - 4529 div: 11345 - 4529 if: 13560 - 4529 div: 11346 - 4529 if: 13483 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529 div: 11304 - 4529 if: 13456 - 4529	div: 11645 - 4529 if: 13476 - 4529 div: 11338 - 4529 if: 13561 - 4529 div: 11288 - 4529 if: 13551 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529 div: 11288 - 4529 if: 13533 - 4529

Ik ben even te lui om de code met de conditional moves te reconstrueren. Ik geloof dat GCC die soms wel genereert (met -m64; met -m32 genereert 'ie 386 compatible code, hoewel je dat ook weer kan tunen natuurlijk) maar hier is dat toch niet het geval.

Wat voor processor gebruikte jij trouwens? Het lijkt er op dat ofwel mijn oude Athlon64 op 2GHz eigenlijk best veel werk verzet per clock cycle, of GCC een stuk efficiëntere code genereert (of een combinatie van beiden).

[.oisyn]

Intel Core 2 Duo. Bottom line is dus dat de if een betere gok is

[ Voor 59% gewijzigd door .oisyn op 26-06-2010 03:26 ]

[Soultaker]

Omdat je er in jouw situatie meer mee wint dan je er bij mij mee verliest, bedoel je? Als je de code aan het schrijven bent, zou je dan misschien beter op de if kunnen gokken, maar om het als latere optimalisatie door te voeren vind ik het nog steeds niet overtuigend, want je blijkt er (afhankelijk van de omstandigheden) mee te kunnen winnen en verliezen. Niet echt nuttige besteding van je tijd dan, of je moet echt niets anders meer kunnen verbeteren aan je programma.

Overigens vind ik ook de oorspronkelijke code beter leesbaar (minder branching, is overzichtelijker, en toevallig ook korter) maar het is wellicht persoonlijk in hoeverre je dat belangrijk vind.

[Verwijderd]

Tijdje niet aanwezig geweest hier, maar ik wil ff laten weten dat ik op een embedded platform zit M68k en werk met de GCC 4.1.1
Op zich is de functie redelijk goed implementeerbaar en na testen heb ik niet veel performance verschil ontdekt in de applicatie.
Maar anyway thanks for the support

Btw GMPlib deed bijna hetzelfde als mijn code alleen veel effiecienter qua memory, aangezien ik voor ieder karakter een byte gebruik.
En zij stoppen (afhankelijk van de input/output ratio) meerdere karakters in een byte

[ Voor 29% gewijzigd door Verwijderd op 21-07-2010 00:52 ]