0

I am trying to implement a bigInt library. I have been checking other libraries like GMP, ttmaht or libtommath but any of them fulfill the requirements of the project (because licenses, because they only use the stack, etc)

I will follow the approach of libtommath (really well documented and written all in C) but I want all stored in the heap. libtommath implements bigInt in an structure like this one:

typedef struct  {
    int used, alloc, sign;
    mp_digit *dp;
} mp_int;

As you can see it has an indirection for accessing the values. (mp_digit are the digits of the big integer). I want to get off the indirection so have some kind of similar struct in the heap where the last element is a mp_digit[] where the size can be different for each instance of mp_int.

I could do it using void* and malloc() knowing that the first X positions are int's with information (used, alloc, sign, etc) and then access to the mp_digit[] knowing the offset but I do not like this idea. I wonder which would be a better approach.

I found other similar questions like this one or this one but they do not store all in the heap so mine is a bit tricky/different.

Thank you,

JomsDev
  • 116
  • 1
  • 9
  • 8
    Please pick one language. – juanchopanza Jul 30 '17 at 07:55
  • change `mp_digit *dp;` to `std::vector dp;` remove `used` and `alloc` – Richard Critten Jul 30 '17 at 08:07
  • 1
    As an example of defining and using such structure you can look at [`LOGPALETTE`](https://msdn.microsoft.com/en-us/library/windows/desktop/dd145040(v=vs.85).aspx) ([some usage example](https://stackoverflow.com/questions/45319996/how-to-construct-a-gdi-bitmap-object-from-a-device-dependent-hbitmap/45337644#45337644)). Basically you just allocate buffer holding struct itself immediately followed up by array of items. – user7860670 Jul 30 '17 at 08:20
  • Your desired ints can't be used as local variables. –  Jul 30 '17 at 09:31
  • @juanchopanza I am going to compile it with a C++ compiler so if we can use some of the benefits/abstractions of C++ it is good. If I have to write this part of the application as a C developer I have no problem with it. – JomsDev Jul 30 '17 at 11:41
  • @RichardCritten It would have an indirection if I use std::vector... – JomsDev Jul 30 '17 at 11:42
  • @JomsDev Ok use a template structure like std::array then – Richard Critten Jul 30 '17 at 12:12
  • @RichardCritten using std::array means knowing the size of each array at compile time. This is not what I need. Sorry – JomsDev Jul 30 '17 at 13:10
  • Then you have an _"XY problem"_ you want dynamic memory but don't want to use the heap. – Richard Critten Jul 30 '17 at 13:11
  • @RichardCritten Maybe I expressed it wrong. I want to use only the heap – JomsDev Jul 30 '17 at 13:12

2 Answers2

2

In C, mp_digit dp[] will mean a flexible array member. This appeared in C99:

typedef struct  {
    int used, alloc;
    signed char sign;
    mp_digit dp[];
} mp_int;

You can allocate memory with malloc(sizeof(mp_int) + alloc * sizeof(mp_digit));; also with realloc.

However there is an obscure thing that might help you save a byte or two here depending on the type of mp_digit - namely, the offset of dp isn't necessarily sizeof(mp_int) but might be less; there is a kludgey macro hack for calculating the actual minimum size to allocate (yet this is still portable).

That definition doesn't work in C++, but you could use a pointer to an incomplete type in C++.

Notice that a flexible array member is not compatible with an 1-byte array such as in here

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
0

in C something like this to create

mp_int *LN_Create(int ndigits, int allocate)
{
    mp_int *ln = calloc(1, sizeof mp_int);

    if (ln != NULL)
    {
        ln->ndigits = ndigits;
        if (allocate)
        {
            ln->dp = calloc(ndigits, sizeof mp_digit);
            ln->alloc = 1;
            if (ln->dp == NULL)
            {
                free(ln);
                ln = NULL;
            }
        }
    }
    return ln;
}

or

mp_int *LN_Create1(int ndigits)
{
    size_t allocsize = sizeof mp_int + (ndigits - 1) * sizeof mp_digit;
    mp_int *ln = malloc(allocsize);

    if (ln != NULL)
    {
        memset(ln, 0, allocsize);
        ln->ndigits = ndigits;
    }
    return ln;
}
0___________
  • 60,014
  • 4
  • 34
  • 74