On Aug 8, 4:54*pm, jack <(E-Mail Removed)> wrote:

> 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;

> *}

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[i] & HI_BIT) >> (N_BITS(WORD) - 1);

words[i] = (words[i] << 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[i] != 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[i] != 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[i] = 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[i], 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[i] != 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));

}

// 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

*/