On Mon, Jan 4, 2010 at 10:52 AM, Cactus <rieman...@googlemail.com> wrote:
>
>
> On Jan 4, 6:38 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>> If it is the latter then here is the relevant code:
>>
>> wsize = usize + vsize;
>>
>> .....
>>
>> if (wp == up || wp == vp)
>> {
>> free_me = wp;
>> free_me_size = w->_mp_alloc;
>> }
>> else
>> (*__gmp_free_func) (wp, w->_mp_alloc * BYTES_PER_MP_LIMB);
>>
>> w->_mp_alloc = wsize;
>> wp = (mp_ptr) (*__gmp_allocate_func) (wsize * BYTES_PER_MP_LIMB);
>> w->_mp_d = wp;
>>
>> Which shows that the only things that can go wrong are:
>>
>> 1) BYTES_PER_MP_LIMB is not 4
>>
>> or
>>
>> 2) something is wrong with __gmp_allocate_func
>>
>> The latter is given by the following code:
>>
>> void * (*__gmp_allocate_func) _PROTO ((size_t)) = __gmp_default_allocate;
>>
>> void *
>> __gmp_default_allocate (size_t size)
>> {
>> void *ret;
>> #ifdef DEBUG
>> size_t req_size = size;
>> size += 2 * BYTES_PER_MP_LIMB;
>> #endif
>> ret = malloc (size);
>> if (ret == 0)
>> {
>> fprintf (stderr, "GNU MP: Cannot allocate memory (size=%u)\n", size);
>> abort ();
>> }
>> ....
>>
>> which is where your message is coming from. But malloc is clearly
>> being fed the right value.
>>
>> To check if the temporary allocation made by the FFT is correct is
>> slightly more work....
>>
>> Bill.
>>
>> 2010/1/4 Bill Hart <goodwillh...@googlemail.com>:
>>
>> > This would be using the FFT. And the FFT should in theory require 4
>> > times the input bit size in order to do the squaring. So to multiply
>> > integers of 2^31 bits, it will request 2^30 bytes of memory. This is
>> > all assuming that the FFT is written to use memory fairly efficiently.
>> > This is in addition to the amount of memory required for the input and
>> > output, which will be a total of 2^31 bits plus 2^32 bits. That makes
>> > a total of just below 8 times the input size, or 2^31 bytes.
>>
>> > It's possible to reduce the FFT memory usage a little below that in
>> > theory, but not much.
>>
>> > Or are you saying that the number of bytes allocated in the actual
>> > output mpz_t is the amount given there?
>>
>> > Bill.
>>
>> > 2010/1/4 Cactus <rieman...@googlemail.com>:
>>
>> >> On Jan 4, 2:43 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>> >>> uintptr_t is a c99 feature. So it "exists" on linux, but formally only
>> >>> in c99 mode. I'm not keen to switch MPIR to c99. But we can define
>> >>> something in mpir.h which on Windows in uintptr_t and on linux is the
>> >>> same size as an mp_limb_t or whatever (I think it is the case that an
>> >>> mp_limb_t should always be the same size as a pointer on the systems
>> >>> we care about).
>>
>> >> If I square numbers of increasin sizes, I get the output:
>>
>> >> 26 134217724
>> >> 27 268435456
>> >> 28 536870911
>> >> 29 1073741821
>> >> 30 2147483645
>> >> GNU MP: Cannot allocate memory (size=4294837280)
>>
>> >> The number on the left is log2(number of bits in the input), the
>> >> number on the right being the number of bits in the result.
>>
>> >> As can be seen it fails for 2^31 input bits because memory for 2^32
>> >> _bytes_ cannot be allocated.
>>
>> >> So it is asking for a lot more memory than its should need.
>>
>> >> mpz_mul asks for memory through the call:
>>
>> >> void *_mpz_realloc (mpz_ptr m, mp_size_t new_alloc)
>>
>> >> and mp_size_t is defined to be an int in gmp-impl.h:
>>
>> >> typedef long int mp_size_t;
>>
>> >> This is 32-bits on Windows so the realloc call will fail as soon as
>> >> 2^32 bytes are asked for.
>>
>> >> The define:
>>
>> >> typedef size_t mp_size_t;
>>
>> >> would seem to be better here.
>>
>> >> But this doesn't explain the excess memory request.
>>
>> >> Brian
>
> This macro (and similar ones) is used in
> #define __GMP_REALLOCATE_FUNC_LIMBS(p, old_size, new_size)
>
> is used in
>
> void *
> _mpz_realloc (mpz_ptr m, mp_size_t new_alloc)
>
> where the arguments to the macro are mp_size_t ints that are 32-bits
> on Windows.
>
> So when the limb number request is above 2^32 / 2^8 = 2^24, the
> allocation will overflow even though the receiving variable is a
> size_t.
>
> It seems clear to me that I need to define mp_size_t as a type that is
> 32-bits on win32 and 64-bits on x64:
>
> typedef size_t mp_size_t;
>
> Is this going to mess up Linux/GCC?
>
> If so I can guard it with an _MSC_VER guard.
mp_size_t is (effectively) defined that way already.
>
> Brian
>
>
>
>
> #define
>
>
>
>
>
>
>
> --
>
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To post to this group, send email to mpir-de...@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/mpir-devel?hl=en.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-de...@googlegroups.com.
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en.
