problem with 128bit integer

J

jack

Hi all,

I have problem in creating a 128 bit integer with 4 unsigned
integers.
My first problem is with shift right and left bits. The function
shiftleft64 , shifts one bit by left. Shiftleft64 works perfectly
well. I did shiftleft128 in the same way, but it doesn't work the way
it has to.

second problem is, i implemented multiplication with 2 unsigned
integers (4*16 bit) for uint64. it works fine. for 128 bit integer, it
does nt work properly since i get 8 unsigned integers (8*16). I have
no idea to do with 8*16bit. The system is old and it supports only
upto 32bit integers. I tried hard, and atlast i posted in to groups.

It would be great if any of you could help me in this issue. Thank
you all.
My implementation is as follows:


#define BIT64 (0x80000000ULL)

typedef struct {
unsigned int lo;
unsigned int hi;
} uint64;

typedef struct {
uint64 lo;
uint64 hi;
} uint128;


uint64
shiftleft64 (uint64 x)
{
unsigned long sbit = x.lo & BIT64;

x.hi <<= 1;
x.lo <<= 1;
if (sbit)
{
x.hi |= 1;
return x;
}

return x;
}


uint128
shiftleft128 (uint128 x)
{
uint64 sbit;
sbit.lo = x.lo.lo & BIT64;
sbit.hi = x.lo.hi & BIT64;

x.hi = shiftleft64(x.hi);
x.lo = shiftleft64(x.lo);

if ((sbit.lo) || (sbit.hi))
{
x.hi.lo |=1;
x.hi.hi |=1;


return x;
}

return x;
}


uint64
mult64 (unsigned int a, unsigned int b)
{
uint64 product;
unsigned int a0, a1;
unsigned int b0, b1;
unsigned int d, d0, d1;
unsigned int e, e0, e1;
unsigned int f, f0, f1;
unsigned int g, g0, g1;
unsigned int sum, carry, roll, pmax;

a1 = a >> 16;
a0 = a - (a1 << 16);

b1 = b >> 16;
b0 = b - (b1 << 16);

d = a0 * b0;
d1 = d >> 16;
d0 = d - (d1 << 16);

e = a0 * b1;
e1 = e >> 16;
e0 = e - (e1 << 16);

f = a1 * b0;
f1 = f >> 16;
f0 = f - (f1 << 16);

g = a1 * b1;
g1 = g >> 16;
g0 = g - (g1 << 16);

sum = d1 + e0 + f0;
carry = 0;

roll = 1 << 14;
roll <<= 2;

pmax = roll - 1;
while (pmax < sum)
{
sum -= roll;
carry ++;
}

product.lo = d0 + (sum << 16);
product.hi = carry + e1 + f1 + g0 + (g1 << 16);

return product;
}
 
T

Thad Smith

jack said:
I have problem in creating a 128 bit integer with 4 unsigned
integers.
My first problem is with shift right and left bits. The function
shiftleft64 , shifts one bit by left. Shiftleft64 works perfectly
well. I did shiftleft128 in the same way, but it doesn't work the way
it has to.

second problem is, i implemented multiplication with 2 unsigned
integers (4*16 bit) for uint64. it works fine. for 128 bit integer, it
does nt work properly since i get 8 unsigned integers (8*16). I have
no idea to do with 8*16bit. The system is old and it supports only
upto 32bit integers. I tried hard, and atlast i posted in to groups.

It would be great if any of you could help me in this issue. Thank
you all.
My implementation is as follows:


#define BIT64 (0x80000000ULL)

typedef struct {
unsigned int lo;
unsigned int hi;
} uint64;
Click to expand...

For portable code, the two components of a 64-bit value must have at least 32
bits, which requires an unsigned long.
typedef struct {
uint64 lo;
uint64 hi;
} uint128;


uint64
shiftleft64 (uint64 x)
{
unsigned long sbit = x.lo & BIT64;
Click to expand...

It's amusing that BIT64 is defined as an unsigned long long. If you have that
type available, you have a native implementation of at least 64 bits and don't
need your uint64 struct. If you want to write portable C90 code, then your
constant and the components should be unsigned long instead of unsigned int.
x.hi <<= 1;
x.lo <<= 1;
if (sbit)
{
x.hi |= 1;
return x;
}

return x;
}


uint128
shiftleft128 (uint128 x)
{
uint64 sbit;
sbit.lo = x.lo.lo & BIT64;
sbit.hi = x.lo.hi & BIT64;

x.hi = shiftleft64(x.hi);
x.lo = shiftleft64(x.lo);

if ((sbit.lo) || (sbit.hi))
{
x.hi.lo |=1;
x.hi.hi |=1;
Click to expand...

There is a problem here. There is no need for assigning and testing sbit.lo
since shiftleft64 takes care of that internal carry.

unsigned long sbit = x.lo.hi & 0x80000000UL;
..
if (sbit)
{
x.hi.lo |= 1;
}
return x;
Click to expand...

It is better style to eliminate this return x; and let the code fall through to
the following one.
}

return x;
}
Click to expand...

I haven't look at the multiply routine.
 
S

suresh

Hi all,

I have problem in creating a 128 bit integer with 4 unsigned
integers.
My first problem is with shift right and left bits. The function
shiftleft64 , shifts one bit by left. Shiftleft64 works perfectly
well. I did shiftleft128 in the same way, but it doesn't work the way
it has to.

second problem is, i implemented multiplication with 2 unsigned
integers (4*16 bit) for uint64. it works fine. for 128 bit integer, it
does nt work properly since i get 8 unsigned integers (8*16). I have
no idea to do with 8*16bit. The system is old and it supports only
upto 32bit integers. I tried hard, and atlast i posted in to groups.

It would be great if any of you could help me in this issue.  Thank
you all.
My implementation is as follows:
Click to expand...

[snipped - shiftleft64, shiftleft128]
uint64
mult64 (unsigned int a, unsigned int b)
Click to expand...

As someone else have pointed out, you would be better of using
unsigned long.
{
        uint64 product;
        unsigned int a0, a1;
        unsigned int b0, b1;
        unsigned int d, d0, d1;
        unsigned int e, e0, e1;
        unsigned int f, f0, f1;
        unsigned int g, g0, g1;
        unsigned int sum, carry, roll, pmax;

     a1 = a >> 16;
     a0 = a - (a1 << 16);
Click to expand...
why not a0 = a & 0xFFFFUL ?
     b1 = b >> 16;
     b0 = b - (b1 << 16);

     d = a0 * b0;
     d1 = d >> 16;
     d0 = d - (d1 << 16);

     e = a0 * b1;
     e1 = e >> 16;
     e0 = e - (e1 << 16);

     f = a1 * b0;
     f1 = f >> 16;
     f0 = f - (f1 << 16);

     g = a1 * b1;
     g1 = g >> 16;
     g0 = g - (g1 << 16);

     sum = d1 + e0 + f0;
     carry = 0;

     roll = 1 << 14;
     roll <<= 2;

     pmax = roll - 1;
Click to expand...
Why not pmax = 0xFFFFUL ?
     while (pmax < sum)
     {
         sum -= roll;
         carry ++;
     }
Click to expand...
why not just carry = sum >> 16
     product.lo = d0 + (sum << 16);
     product.hi = carry + e1 + f1 + g0 + (g1 << 16);

     return product;
 }
Click to expand...

Coming back to your 126 bit multiplication, you can use this mul64
function to multiple 4 32 bit numbers (128 bit) applying the similar
logic implemented above.
 
T

Tom St Denis

Hi all,

I have problem in creating a 128 bit integer with 4 unsigned
integers.
My first problem is with shift right and left bits. The function
shiftleft64 , shifts one bit by left. Shiftleft64 works perfectly
well. I did shiftleft128 in the same way, but it doesn't work the way
it has to.
Click to expand...


Why not check out the public domain LibTomMath project at

http://libtom.org/?page=features&newsitems=5&whatfile=ltm

It's written in portable C, will work on 16-bit platforms [as well as
32 and 64-bit] and handles numbers of arbitrary size. It's also
public domain (well the new maintainers are talking about releasing it
under an OSI approved license ... but the versions I maintained are
Public Domain).

Tom
 
G

Gene

Hi all,

I have problem in creating a 128 bit integer with 4 unsigned
integers.
My first problem is with shift right and left bits. The function
shiftleft64 , shifts one bit by left. Shiftleft64 works perfectly
well. I did shiftleft128 in the same way, but it doesn't work the way
it has to.

second problem is, i implemented multiplication with 2 unsigned
integers (4*16 bit) for uint64. it works fine. for 128 bit integer, it
does nt work properly since i get 8 unsigned integers (8*16). I have
no idea to do with 8*16bit. The system is old and it supports only
upto 32bit integers. I tried hard, and atlast i posted in to groups.

It would be great if any of you could help me in this issue.  Thank
you all.
My implementation is as follows:

#define BIT64 (0x80000000ULL)

typedef struct {
unsigned int lo;
unsigned int hi;

} uint64;

typedef struct {
uint64 lo;
uint64 hi;

} uint128;

uint64
shiftleft64 (uint64 x)
 {
     unsigned long sbit = x.lo & BIT64;

     x.hi <<= 1;
     x.lo <<= 1;
     if (sbit)
     {
         x.hi |= 1;
         return x;
     }

     return x;
 }

uint128
shiftleft128 (uint128 x)
 {
        uint64 sbit;
        sbit.lo = x.lo.lo & BIT64;
        sbit.hi = x.lo.hi & BIT64;

        x.hi = shiftleft64(x.hi);
        x.lo = shiftleft64(x.lo);

        if ((sbit.lo) || (sbit.hi))
        {
                x.hi.lo |=1;
                x.hi.hi |=1;

                return x;
        }

        return x;
 }

uint64
mult64 (unsigned int a, unsigned int b)
{
        uint64 product;
        unsigned int a0, a1;
        unsigned int b0, b1;
        unsigned int d, d0, d1;
        unsigned int e, e0, e1;
        unsigned int f, f0, f1;
        unsigned int g, g0, g1;
        unsigned int sum, carry, roll, pmax;

     a1 = a >> 16;
     a0 = a - (a1 << 16);

     b1 = b >> 16;
     b0 = b - (b1 << 16);

     d = a0 * b0;
     d1 = d >> 16;
     d0 = d - (d1 << 16);

     e = a0 * b1;
     e1 = e >> 16;
     e0 = e - (e1 << 16);

     f = a1 * b0;
     f1 = f >> 16;
     f0 = f - (f1 << 16);

     g = a1 * b1;
     g1 = g >> 16;
     g0 = g - (g1 << 16);

     sum = d1 + e0 + f0;
     carry = 0;

     roll = 1 << 14;
     roll <<= 2;

     pmax = roll - 1;
     while (pmax < sum)
     {
         sum -= roll;
         carry ++;
     }

     product.lo = d0 + (sum << 16);
     product.hi = carry + e1 + f1 + g0 + (g1 << 16);

     return product;
 }
Click to expand...

I can't follow what your multiply is trying to do. Here's how I'd do
it. The code is only barely tested.

#include <stdio.h>

typedef unsigned long WORD;
typedef unsigned short HALF_WORD;

#define N_BITS(X) (8 * sizeof(X))
#define HI_BIT (1ul << (N_BITS(WORD) - 1))
#define HALF_WORD_BITS (0xfffful)

// 128-bit integer rep
typedef struct uint128_s {
WORD words[4];
} uint128;

#define ARRAY_SIZE(A) (sizeof A / sizeof A[0])

// Shift the given n words left one position. Return the carry.
static WORD shift_left(WORD *words, int n)
{
WORD i, carry, new_carry;

for (carry = i = 0; i < n; i++) {
new_carry = (words & HI_BIT) >> (N_BITS(WORD) - 1);
words = (words << 1) | carry;
carry = new_carry;
}
return carry;
}

// Store hex string rep of w into buffer. Return the buffer.
static char *word_as_hex_string(char *buf, WORD w)
{
sprintf(buf, "%08lx", w);
return buf;
}

// Store hex string rep of n given words into buffer. Return the
buffer.
static char *words_as_hex_string(char *buf, WORD *words, int n)
{
int iw, ib;

for (ib = 0, iw = n - 1; iw >= 0; ib += N_BITS(WORD) / 4, iw--)
word_as_hex_string(buf + ib, words[iw]);
return buf;
}

// Return non-0 iff all n given words are zero.
static int words_zero_p(WORD *words, int n)
{
int i;

for (i = 0; i < n; i++)
if (words != 0)
return 0;
return 1;
}

// Accumulate a into the words at r.
// Return 1 on overflow, else zero.
static int accum(WORD *r, int n, WORD a)
{
int i;

WORD x = r[0];
r[0] = x + a;
if (r[0] < x || r[0] < a) {
for (i = 1; i < n; i++)
if (++r != 0)
return 0;
return 1; // overflow
}
return 0;
}

// Multiply a and b to form result in r[0] and r[1]. Can't overflow!
static void mul2(WORD *r, WORD a, WORD b)
{
WORD a0 = a & HALF_WORD_BITS;
WORD b0 = b & HALF_WORD_BITS;
WORD a1 = a >> N_BITS(HALF_WORD);
WORD b1 = b >> N_BITS(HALF_WORD);
WORD a0b1 = a0 * b1;
WORD a1b0 = a1 * b0;
WORD a0b0 = a0 * b0;
WORD a1b1 = a1 * b1;
WORD c = a0b1 + a1b0;
WORD cc = (c < a0b1 || c < a1b0);
WORD c0 = (c << N_BITS(HALF_WORD));
WORD c1 = (c >> N_BITS(HALF_WORD)) + (cc << N_BITS(HALF_WORD));
r[0] = a0b0 + c0; // carry out of r0 is possible
r[1] = a1b1 + c1 + (r[0] < a0b0 || r[0] < c0);
}

// Grade school long multiplication. Return non-zero iff
// there was an overflow.
static int multiply_words(WORD *r, WORD *a, WORD *b, int n)
{
int i, j, overflow = 0;
WORD tmp[2];

// Zero the result.
for (i = 0; i < n; i++)
r = 0;

// Cross-product multiplication of words of operands.
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
// Destination of current word pair multiplication.
int d = i + j;
if (d < n) {
// Destination exists. Multiply and accumulate.
mul2(tmp, a, b[j]);
overflow += accum(r + d, n - d, tmp[0]);
if (d < n - 1)
overflow += accum(r + d + 1, n - d - 1, tmp[1]);
else if (tmp[1] != 0)
// No place for hi word and it's non-0, so overflow.
overflow++;
}
else if (a != 0 && b[j] != 0)
overflow++;
}
}
return overflow;
}

// ---- visible operations

// Return non-0 iff val is zero.
int uint128_zero_p(uint128 *val)
{
return words_zero_p(val->words, ARRAY_SIZE(val->words));
}

// Shift the value given by argument pointer one place left.
// Return the pointer.
uint128 *shift_uint128_left(uint128 *val)
{
shift_left(val->words, ARRAY_SIZE(val->words));
return val;
}

// Return the given value shifted one place to the left.
uint128 uint128_left_shifted(uint128 val)
{
return *shift_uint128_left(&val);
}

// Multiply the values at a and b into the one at r. Return non-0
// iff there was an overflow in the multiplication.
int multiply_uint128(uint128 *r, uint128 *a, uint128 *b)
{
return multiply_words(r->words, a->words, b->words, ARRAY_SIZE(r-
words));
Click to expand...
}

// Fill the given buffer (at least 33 chars) with hex string rep
// of the given value and return the buffer.
char *uint128_as_hex_string(char *buf, uint128 *val)
{
return words_as_hex_string(buf, val->words, ARRAY_SIZE(val->words));
}

// Some cursory testing.
int main(void)
{
int i;
char buf[33];
uint128 one[1] = {{{ 1u, 0, 0, 0 }}};
uint128 seven[1] = {{{ 7u, 0, 0, 0 }}};
uint128 fs[1] = {{{0xffffffffu, 0, 0, 0}}};
uint128 x[1], f[1], f_new[1];

printf("Repeated shift test:\n");
*x = *one;
while (!uint128_zero_p(x)) {
printf("%s\n", uint128_as_hex_string(buf, x));
shift_uint128_left(x);
}

printf("\nFactorial test:\n");
*x = *f_new = *f = *one;
while (1) {
x->words[0]++;
if (multiply_uint128(f_new, x, f)) {
printf("overflow: %lu %s\n", x->words[0],
uint128_as_hex_string(buf, f_new));
break; // break on overflow
}
printf("%lu %s\n", x->words[0], uint128_as_hex_string(buf,
f_new));
*f = *f_new;
}

printf("Repeated squaring of 7 test:\n");
*f = *seven;
for (i = 1; ; i++) {
if (multiply_uint128(f_new, f, f)) {
printf("overflow: %d %s\n", i, uint128_as_hex_string(buf,
f_new));
break;
}
printf("%d %s\n", i, uint128_as_hex_string(buf, f_new));
*f = *f_new;
}

printf("ffffffff * ffffffff test:\n");
multiply_uint128(f_new, fs, fs);
printf("%s\n", uint128_as_hex_string(buf, f_new));

return 0;
}

/*
Correct values of factorial:
CL-USER> (dotimes (i 36) (format t "~d ~x~%" i (f i)))
0 1
1 1
2 2
3 6
4 18
5 78
6 2D0
7 13B0
8 9D80
9 58980
10 375F00
11 2611500
12 1C8CFC00
13 17328CC00
14 144C3B2800
15 13077775800
16 130777758000
17 1437EEECD8000
18 16BEECCA730000
19 1B02B9306890000
20 21C3677C82B40000
21 2C5077D36B8C40000
22 3CEEA4C2B3E0D80000
23 57970CD7E2933680000
24 83629343D3DCD1C00000
25 CD4A0619FB0907BC00000
26 14D9849EA37EEAC91800000
27 232F0FCBB3E62C3358800000
28 3D925BA47AD2CD59DAE000000
29 6F99461A1E9E1432DCB6000000
30 D13F6370F96865DF5DD54000000
31 1956AD0AAE33A4560C5CD2C000000
32 32AD5A155C6748AC18B9A580000000
33 688589CC0E9505E2F2FEE5580000000
34 DE1BC4D19EFCAC82445DA75B00000000
35 1E5DCBE8A8BC8B95CF58CDE17100000000
*/

/*
Correct repeated squares of 7:
CL-USER> (let ((x 7)) (dotimes (i 6) (setq x (* x x)) (format t "~d ~x~
%" (1+ i) x)))
1 31
2 961
3 57F6C1
4 1E39A5057D81
5 3918FA8303C33586E913B01
6 CBC21FE4561C8D63B78E780E1341E199417C8C0BB7601
*/
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Python code problem 2
retriving escape unicode sequences from files ... 1
geting error as unxpected symbol read: ". in array initialization 0
corrupt zip files 10
retriving escape unicode sequences from files ... 1
some OT: how to solve this kind of problem in our program? 12
help with the testbench 2
Need help with a dictionary class... 1

Members online

No members online now.
Total: 290 (members: 1, guests: 289)
Robots: 381

Forum statistics

Threads
473,954
Messages
2,570,116
Members
46,704
Latest member
BernadineF

Latest Threads

Top