CODEWITHSUNDEEP
cstringnumbers
pki
pki

Reputation: 153

Converting a long hexadecimal string to a decimal string

I would need to figure out a way to do the following in standard C. Assume we are given a string representing a hexadecimal number with say n digits. We want to convert this to a string representing the same number in decimal. The strings could have an arbitrary number of digits. What's at least easy to deduce is that the decimal string needs <= 2n letters.

Once we reach the size limit for numbers that the machine can handle, then the length of the string becomes quite irrelevant, so a hexadecimal number with 100 digits should be just as easy/hard to convert as one with 1000 digits i.e. the same algorithm should work on both as it has to work in chunks.

Has anyone here thought about this? What's really annoying is that large powers of 2 have nonzero digits down to the first order, so any element in the hexadecimal sequence can affect the last digit in decimal...

I could only find questions where someone wanted a string converted to a number or a number to a string in some base. If someone wonders why I would need this. I'm playing around with arbitrary precision numbers and the most economical format for storing numbers in is base 256, so I need to print numbers given in this form (or equivalently any hexadecimal).

EDIT: So I implemented a conversion function and I'll share it here if anyone else might ever need it. This was very quick an dirty and a better implementation would of course start by replacing the digits buffer in the struct by something that gets dynamically allocated. Since all arithmetic happens in the "add" function it would then be easy to realloc this buffer to something bigger if an addition overflows. The output buffer size is always simple to assign, since any hexadecimal number converts to a decimal number with less or equal to twice the digits.

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

#define MAXLEN 1000


struct number {
    unsigned char digits[MAXLEN];
    unsigned int num_digits;
};

int add(struct number *, struct number *, struct number *);
int mult(struct number *, struct number *, struct number *);
int power(struct number *, unsigned int, struct number *);
void print_number(struct number *, char *);
void dec(struct number *);

void hex2dec(char *hex, char *outbuf)
{
    int n;
    char *s;
    struct number decrep;
    struct number twopow;
    struct number digit;

    decrep.num_digits = 0;

    n = strlen(hex);
    s = hex;

    while(--n > -1) {
        /* weight of digit */
        twopow.num_digits = 2;
        twopow.digits[0] = 6;
        twopow.digits[1] = 1;
        power(&twopow, n, &twopow);

        /* Extract digit */
        if(*s <= '9' && *s >= '0') {
            digit.digits[0] = *s - '0';
            digit.num_digits = 1;
        } else if(*s <= 'f' && *s >= 'a') {
            digit.digits[0] = *s - 'a';
            digit.digits[1] = 1;
            digit.num_digits = 2;
        } else if(*s <= 'F' && *s >= 'A') {
            digit.digits[0] = *s - 'A';
            digit.digits[1] = 1;
            digit.num_digits = 2;
        }

        s++;

        mult(&digit, &twopow, &digit);
        add(&decrep, &digit, &decrep);
    }

    /* Convert decimal number to a string */
    if(decrep.num_digits == 0) {
        *outbuf = '0';
        *(++outbuf) = '\0';
        return;
    }

    for(n = decrep.num_digits-1; n >= 0; n--) {
        *(outbuf++) = '0' + decrep.digits[n];
    }

    *outbuf = '\0';
}

int main(void)
{
    char buf[1000];

    hex2dec("FFEa4334234FABCD", buf);

    printf("%s", buf);
    return 0;
}

void copy_number(struct number *dst, struct number *src)
{
    int i;

    for(i = 0; i < src->num_digits; i++) dst->digits[i] = src->digits[i];

    dst->num_digits = src->num_digits;
}

int power(struct number *a, unsigned int n, struct number *b)
{
    struct number atmp;

    /* Are we exponentiating by 0? */
    if(n == 0) {
        b->num_digits = 1;
        b->digits[0] = 1;
        return 0;
    }

    copy_number(&atmp, a);

    while(--n > 0) {
        mult(&atmp, a, &atmp);
    }

    copy_number(b, &atmp);
    return 0;
}

int mult(struct number *a, struct number *b, struct number *c)
{
    struct number btmp;
    struct number ctmp;
    struct number *t;

    /* Are we multiplying by 0? */
    if(a->num_digits == 0 || b->num_digits == 0) {
        c->num_digits = 0;
        return 0;
    }

    if(a->num_digits < b->num_digits) {
        t = a;
        a = b;
        b = t;
    }

    copy_number(&btmp, b);
    copy_number(&ctmp, a);

    while(1) {
        /* Are we multiplying by 1? */
        if(btmp.num_digits == 1 && btmp.digits[0] == 1) {
            break;
        }

        add(&ctmp, a, &ctmp);
        dec(&btmp);
    }

    copy_number(c, &ctmp);

    return 0;
}

int add(struct number *a, struct number *b, struct number *c)
{
    int i, j;
    int carry;

    struct number *t;

    if(a->num_digits < b->num_digits) {
        t = a;
        a = b;
        b = t;
    }

    for(i = 0, carry = 0; i < a->num_digits; i++) {

        if(i >= b->num_digits) j = a->digits[i]+carry;
        else j = a->digits[i]+b->digits[i]+carry;

        if(j > 9) {
            j -= 10;
            carry = 1;
        } else {
            carry = 0;
        }

        c->digits[i]=j;
    }

    /* Did we overflow? */
    if(carry > 0 && i == MAXLEN) return -1;

    /* Carry over from last addition? */
    if(carry > 0) {
        c->digits[i] = carry;
        c->num_digits = a->num_digits+1;
    } else {
        c->num_digits = a->num_digits;
    }

    return 0;
}

void print_number(struct number *a, char *buf)
{
    int i;

    if(a->num_digits == 0) {
        printf("0");
        return;
    }

    for(i = a->num_digits-1; i >= 0; i--) {
        *(buf++) = '0' + a->digits[i];
    }

    *buf = '\0';
}

void dec(struct number *a)
{
    int i;

    for(i = 0; i < a->num_digits; i++) {
        if(a->digits[i] > 0) {
            a->digits[i]--;
            break;
        }

        a->digits[i] = 9;
    }

    /* Did number of digits get lower */
    if(i == a->num_digits -1 && a->digits[i] == 0) {
        for(i = a->num_digits - 1; i >= 0; i--) {
            if(a->digits[i] != 0) {
                a->num_digits = i + 1;
                break;
            }
        }
    }
}

Upvotes: 1

Views: 2516

Answers (1)

SB5
SB5

Reputation: 1

Please note there is a bug in this code. As soon as the HEX string contains a 0 ! this snippet :

/* Extract digit */
if(*s <= '9' && *s >= '0') {
    digit.digits[0] = *s - '0';
    digit.num_digits = 1;
} else if(*s <= 'f' && *s >= 'a') {

gives digits[0] = 0; num_digites = 1; But later in the mult() function there is the snipet :

if(a->num_digits == 0 || b->num_digits == 0) {
    c->num_digits = 0;
    return 0;
}

that test 0 by num_digits == 0. So I suggest to replace in the first function the snippet with :

if(*s == '0') {
    digit.digits[0] = *s - '0';
    digit.num_digits = 0;
}else if(*s <= '9' && *s > '0') {
    digit.digits[0] = *s - '0';
    digit.num_digits = 1;
} else if(*s <= 'f' && *s >= 'a') {

looks to work fine for me. You can compare the result on this site : http://www.statman.info/conversions/hexadecimal.php

Upvotes: 0

Related Questions