Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > problem with 128bit integer

Reply
Thread Tools

problem with 128bit integer

 
 
jack
Guest
Posts: n/a
 
      08-08-2010
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;
}
 
Reply With Quote
 
 
 
 
Thad Smith
Guest
Posts: n/a
 
      08-09-2010
jack wrote:

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


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;


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;


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;


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

> }
>
> return x;
> }
>


I haven't look at the multiply routine.

--
Thad
 
Reply With Quote
 
 
 
 
suresh
Guest
Posts: n/a
 
      08-09-2010
On Aug 9, 1:54*am, 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:
>


[snipped - shiftleft64, shiftleft128]

>
> uint64
> mult64 (unsigned int a, unsigned int b)


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

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;

Why not pmax = 0xFFFFUL ?

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

why not just carry = sum >> 16

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


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.
 
Reply With Quote
 
Tom St Denis
Guest
Posts: n/a
 
      08-09-2010
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.



Why not check out the public domain LibTomMath project at

http://libtom.org/?page=features&new...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

 
Reply With Quote
 
Gene
Guest
Posts: n/a
 
      08-10-2010
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
*/
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Cannot set 128bit WEP Key for Compaq W200? Anderas Klein Wireless Networking 2 07-29-2009 12:52 AM
WPA or WEP-128bit for Home Wireless? DRK Wireless Networking 13 10-10-2008 10:29 PM
How length should the key be at least for WEP(64, 128bit), WPA and WPA2? redsung@gmail.com Wireless Networking 1 11-17-2005 06:00 AM
128bit cipher strenght emcryption Zoli Computer Support 2 03-18-2005 07:38 AM
ipv6 / 128bit crypto chris Cisco 0 07-11-2003 02:23 AM



Advertisments