Arbitrary precision number to ascii in c

Question

I've a uint8_t * array which contains an arbitrary precision number bigendian encoded.

I'd like to get its decimal Ascii representation. So I'd need to write a function that returns a char *.

The environment i'm using does not allow me to import any arbitrary precision library due to hardware limitations.

I'm sure there is something i can read to easily implement it.

For example the number defined by the following hex d53ceb9d32c6ca06 should be represented by 15365415089075571206.

It depends on how much conversion you need between text and number. If you use radix `100` instead of `256` the text output is almost trivial, but there is a trade-off because arithmetical computations with your bignum will need to use the less efficient `%` instead of `&` to separate partial sums, products, etc. — Weather Vane, Oct 15 '17 at 19:06
@MatteoItalia maybe i'm missing something. You want me to divide the whole thing by 10 as many times as it is needed util the quotient (last 8 bits?) is >10 and use the remainders to build up the string ? — Andrea Baccega, Oct 15 '17 at 19:25
@AndreaBaccega unless you do what I suggested earlier, you *will* need to divide the whole thing by `10` until there is nothing left. I write from experience because I have written *two* bignum libraries: one as arbitrary integer size, and another with arbitrary integer and arbitrary fraction sizes — Weather Vane, Oct 15 '17 at 19:30
@WeatherVane are your library opensource? I understand the algorithm but i'm not a good c developer (still i need to do it in C) — Andrea Baccega, Oct 15 '17 at 19:34
Nope sorry, just private ;) Publishing is always an order of magnitude more difficult. — Weather Vane, Oct 15 '17 at 19:35
There are lots of implementations of mp integer arithmetic out there, in portable C and usable in constrained environments. You can just rip out what you need from those quite easily. — pvg, Oct 15 '17 at 19:37
@AndreaBaccega just googling 'small multiple precision c library' finds a bunch, not necessarily all small but there are libraries, lists of libraries, articles on how to write such libraries. It's rich pickings. — pvg, Oct 15 '17 at 21:03

Daniel Martin · Answer 1 · 2017-10-16T10:06:31.360

Here's a method that should work. Note that it destructively modifies the bigint that you pass to it, so if you care about the value there, copy it to a temporary scratch buffer before calling the method.

Also, this isn't the most optimized version you could write, but if you're asking how to do it on here you probably aren't concerned yet about micro-optimization with this.

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

bool is_zero(uint8_t *bigi_data, int bigi_size) {
    int i = 0;

    while((i < bigi_size) && (bigi_data[i] == 0)) {
        i++;
    }
    return (i >= bigi_size);
}

uint8_t bigdivmod(uint8_t *bigi_data, int bigi_size, uint8_t divisor) {
    int i = 0;
    uint16_t ans = 0;

    while((i < bigi_size) && (bigi_data[i] == 0)) {
        i++;
    }
    for (; i < bigi_size; i++) {
        ans = ans*256 + bigi_data[i];
        bigi_data[i] = ans / divisor;
        ans = ans % divisor;
    }
    return (uint8_t)ans;
}

static const char *digits = "0123456789abcdefghijklmnopqrstuvwxyz";

char *bigitoa(uint8_t *bigi_data, int bigi_size, char *out, int base) {
    /* Assumes that "out" has enough room. DESTRUCTIVE TO BIGI, so copy */
    /* if you care about the value */
    /* Only really works for non-negative values */
    int i = 0;
    uint8_t swp;
    int j;

    if ((base < 2) || (base > 36)) {
        return NULL;
    }

    if (is_zero(bigi_data, bigi_size)) {
        out[0] = '0';
        out[1] = '\0';
        return out;
    }

    while (!is_zero(bigi_data, bigi_size)) {
        out[i++] = digits[bigdivmod(bigi_data, bigi_size, base)];
    }
    out[i] = 0;
    for (j = 0; j < i/2; j++) {
        swp = out[i - 1 - j];
        out[i - 1 - j] = out[j];
        out[j] = swp;
    }

    return out;
}

int main(int argc, char *argv[]) {
    uint8_t test_data[] = { 0xd5, 0x3c, 0xeb, 0x9d, 0x32, 0xc6, 0xca, 0x06 };
    int test_data_len = sizeof(test_data);
    char *p;

    /* Times 3 because we can use three digits to represent 256. If changing */
    /* the base below from "10", change this factor. */
    p = malloc(3*test_data_len + 1);

    printf("Test data works out to %s\n",
           bigitoa(test_data, test_data_len, p, 10));

    return 0;
}

Arbitrary precision number to ascii in c

1 Answers1