problem with 128bit integer

Discussion in 'C Programming' started by jack, Aug 8, 2010.

  1. jack

    jack Guest

    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;
    }
    jack, Aug 8, 2010
    #1
    1. Advertising

  2. jack

    Thad Smith Guest

    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
    Thad Smith, Aug 9, 2010
    #2
    1. Advertising

  3. jack

    suresh Guest

    On Aug 9, 1:54 am, jack <> 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.
    suresh, Aug 9, 2010
    #3
  4. jack

    Tom St Denis Guest

    On Aug 8, 4:54 pm, jack <> 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&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
    Tom St Denis, Aug 9, 2010
    #4
  5. jack

    Gene Guest

    On Aug 8, 4:54 pm, jack <> 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 & 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));

    }

    // 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
    */
    Gene, Aug 10, 2010
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?Sm9l?=

    CType(x,Integer) vs. Integer.Parse(x)

    =?Utf-8?B?Sm9l?=, Feb 6, 2006, in forum: ASP .Net
    Replies:
    7
    Views:
    5,948
    =?Utf-8?B?RGF2aWQgQW50b24=?=
    Feb 7, 2006
  2. =?ISO-8859-1?Q?Thomas_Gagn=E9?=

    No Math.min(Integer, Integer)?

    =?ISO-8859-1?Q?Thomas_Gagn=E9?=, Jul 29, 2003, in forum: Java
    Replies:
    0
    Views:
    502
    =?ISO-8859-1?Q?Thomas_Gagn=E9?=
    Jul 29, 2003
  3. Sebastian Stelzer

    How do I add an Integer to another Integer?

    Sebastian Stelzer, Oct 14, 2004, in forum: Java
    Replies:
    2
    Views:
    490
    Yu SONG
    Oct 15, 2004
  4. Sebastian Stelzer

    How do I add an Integer to another Integer?

    Sebastian Stelzer, Oct 14, 2004, in forum: Java
    Replies:
    6
    Views:
    45,404
    JavaBean2010
    Apr 7, 2010
  5. RonF
    Replies:
    1
    Views:
    158
Loading...

Share This Page