Help: bitwise operations on a 56 bit word 
Author Message
 Help: bitwise operations on a 56 bit word

: Hello,

:     I have a 56 bit word that I need to do bitwise operations on (namely,
: shift operations and complements.)
:     How do I do this in C?  If I want to take the 2s complement and I split
: it up into two 32 bit words, there'll be a possible shift when I add one to
: the lower word (after a complement).  How do I catch the shift in order to
: carry it over to the other word?  Does C provide for this type of thing?
:     Any comments or ideas on doing bitwise operations on 'longer than int'
: words would be much appreciated.

: Thanks,

: T

--
****************begin r.s. response*******************

        one could not reasonably
        expect a language like
                the 'c' programming language
        to provide such indefinite capabilities
        ...
        if integer data types are too small
        here ...
        either of finding,  or writing,
        a library ( of functions,  or macros )
        to do this,
        is appropriate ...

****************end r.s. response*********************
Ralph Silverman



Fri, 01 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word


Quote:


>: Hello,

>:     I have a 56 bit word that I need to do bitwise operations on (namely,
>: shift operations and complements.)
>:     How do I do this in C?  If I want to take the 2s complement and I split
>: it up into two 32 bit words, there'll be a possible shift when I add one to
>: the lower word (after a complement).  How do I catch the shift in order to
>: carry it over to the other word?  Does C provide for this type of thing?
>:     Any comments or ideas on doing bitwise operations on 'longer than int'
>: words would be much appreciated.

>: Thanks,

>: T

>--
>****************begin r.s. response*******************

>    one could not reasonably
>    expect a language like
>            the 'c' programming language
>    to provide such indefinite capabilities

More useless bullshit from Silverman. A 56 bit word can be readily manipulated
using two unsigned long quantities. It's not the same as providing a
general-purpose multi-precision library.

My guess is that this fellow is trying to manipulate DES keys.

Now, to answer the question, how do you overflow shifted bits from one word to
another? What you do is you shift in the opposite direction and save
the result. For example:

    void shift_left(unsigned long a[], int n, int shift, int do_rotate)
    {
        unsigned long carry_in = 0, carry_out;
        int i;

        for (i = 0; i < n; i++) {
            carry_out = (a[i] & 0xffffffful) >> (32 - shift);
            a[i] = ((a[i] << shift) | carry_in) & 0xfffffful;
            carry_in = carry_out;
        }

        if (do_rotate)
            a[0] |= carry_out;
    }

See how the carry out is computed by shifting bits in the opposite direction?
This stores bits in a handy form that can just be ORed into the next word.

The   & 0xfffffffful  operations force results to 32 bits in case unsigned long
is larger than 32 bits.  A good compiler will get rid of these operations if
unsigned long is exactly 32 bits.

I would tailor the routine to your particular needs. E.g. if n is small, you
can unroll the loop manually. If shift is fixed, replace it by a constant.
Etc.



Fri, 01 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

: Now, to answer the question, how do you overflow shifted bits from one word
: to another? What you do is you shift in the opposite direction and save
: the result. For example:

:     void shift_left(unsigned long a[], int n, int shift, int do_rotate)
:     {
:       unsigned long carry_in = 0, carry_out;
:       int i;

:       for (i = 0; i < n; i++) {
:           carry_out = (a[i] & 0xffffffful) >> (32 - shift);
:           a[i] = ((a[i] << shift) | carry_in) & 0xfffffful;
:           carry_in = carry_out;
:       }

:       if (do_rotate)
:           a[0] |= carry_out;
:     }

  More non-functional code from Kylheku.
  Kylheku assumes unsigned long has a size of 32 bits.
  Kylheku also "ands" by an improper value in the line containing the
  shift right.
  Similarly her "ands" by an improper value in the line containing the
  shift left.
  He fails to document that a[0] is the LSWord
  He fails do document what any of his input variables represent.
  His technique fails for negative numbers.

: The  & 0xfffffffful  operations force results to 32 bits in case unsigned
: long is larger than 32 bits.

  If unsigned long is > 32 bits, then the technique presented above
truncates the upper bits.

: I would tailor the routine to your particular needs.

  I recommending finding code that works.

--
<---->



Wed, 06 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word


 >   Kylheku assumes unsigned long has a size of 32 bits.
So what?
 >   Kylheku also "ands" by an improper value in the line containing the
 >   shift right.
What is improper with 0xffffffful, considering the assumption?
 >   Similarly her "ands" by an improper value in the line containing the
 >   shift left.
What is improper with 0xfffffful, considering the assumption?


 > : I would tailor the routine to your particular needs.
 >
 >   I recommending finding code that works.

Why not provide it?
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/



Fri, 08 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

[ ... ]

Quote:
>   Kylheku assumes unsigned long has a size of 32 bits.

Kaz was never challenged to write a portable version of this.

Your "portable assembler" has no predefined word size then?

[ ... ]



Fri, 08 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

:   More non-functional code from Kylheku.
:   Kylheku assumes unsigned long has a size of 32 bits.

Ok, he could go to limits.h and improve that.  Try finding limits.h in
your assembler, moron.

:   Kylheku also "ands" by an improper value in the line containing the
:   shift right.
:   Similarly her "ands" by an improper value in the line containing the
:   shift left.

I'm not even going to argue.  Unless you want to claim that it _cannot_
be done correctly, your argument is meaningless.

:   He fails to document that a[0] is the LSWord
:   He fails do document what any of his input variables represent.

Well, clearly if he doesn't comment it such that you are satisfied,
it won't work, will it?

:   His technique fails for negative numbers.

It also fails depending on the endianness of the machine.  This sort of
thing is why libraries to perform such tasks are written that have the
same interface across platforms, and this same sort of thing is why
no assembler will ever be 'portable.'

:   I recommending finding code that works.

Then obviously we can't write it in PASM, because that won't work without
a vaporware assembler.

--
John J. Adelsberger III                 St. Louis, MO:  (314)434-3067  

"I'm the root of all that's evil, but you can call me Cookie."  - {*filter*}hound
                                                                  Gang



Sat, 09 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

: >   Kylheku assumes unsigned long has a size of 32 bits.

: Kaz was never challenged to write a portable version of this.

  C pushers constantly write non-portable code while proclaiming to the
world that C is portable.

  They misrepresent reality in order to promote their religion.

: Your "portable assembler" has no predefined word size then?

  It does.  Implementation provides security and portability.



Sat, 09 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word


Quote:

> >   Kylheku assumes unsigned long has a size of 32 bits.
>So what?
> >   Kylheku also "ands" by an improper value in the line containing the
> >   shift right.
>What is improper with 0xffffffful, considering the assumption?

Because it should be 0xfffffffful---the intended effect is to reduce the
value modulo 2^32. Indeed, Scott Nudds has applied himself well. I'm surprised
he caught the errors.

What is improper with 0xfffffful is that it will send pieces of your data
to the great bit bucket in the sky. My apologies.

I basically code such things by twitching my finger randomly over the 'f'.
Then I stand back and eyeball the constant to see whether it has approximately
the right length. About 3/4 inches is good for a 32 bit constant on most
terminals, give or take a few six{*filter*}ths.



Sun, 10 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word


Quote:


>: Now, to answer the question, how do you overflow shifted bits from one word
>: to another? What you do is you shift in the opposite direction and save
>: the result. For example:

>:     void shift_left(unsigned long a[], int n, int shift, int do_rotate)
>:     {
>:   unsigned long carry_in = 0, carry_out;
>:   int i;

>:   for (i = 0; i < n; i++) {
>:       carry_out = (a[i] & 0xffffffful) >> (32 - shift);
>:       a[i] = ((a[i] << shift) | carry_in) & 0xfffffful;
>:       carry_in = carry_out;
>:   }

>:   if (do_rotate)
>:       a[0] |= carry_out;
>:     }

>  More non-functional code from Kylheku.

What ``more'' are you talking about? Cite a previous example of non-working
code to back up your claim, {*filter*}.

Yes it is non-functional. I typed this ``off the cuff of my sleeve'' so
to speak. The masks are gapingly wrong, they should be:

    0xfffffffful        /* eight f's */

Other than that, I can't see anything wrong.

Quote:
>  Kylheku assumes unsigned long has a size of 32 bits.

Where?

Quote:
>  Kylheku also "ands" by an improper value in the line containing the
>  shift right.

Yes, I admit my mistake.

Quote:
>  Similarly her "ands" by an improper value in the line containing the
>  shift left.

And you just misspelled 'he' as 'her'. So what?

Quote:
>  He fails to document that a[0] is the LSWord

It isn't.

Quote:
>  He fails do document what any of his input variables represent.

It's your problem that you don't understand it. The purpose of the
code is pretty obvious.

Quote:
>  His technique fails for negative numbers.

What negative numbers? Are you smoking dope?  You mean negative shifts?  It is
not intended to be used with negative shifts. That's why it's called
``shift_left'' rather than ``shift_bidirectional'' or some such thing. The C
language doesn't even define what happens when a negative operand appers on the
left side of the << operator, you dimwit.  The result is implementation
defined. Okay, so the interface could be changed so that the shift amount is an
unsigned int. (But that won't prevent someone from trying to pass in a negative
number which will get reduced to an unsigned one).

In a real project, I would definitely assert the preconditions:

    assert(shift > 0 && shift < 32);

Happy?

Quote:

>: The  & 0xfffffffful  operations force results to 32 bits in case unsigned
>: long is larger than 32 bits.

See? That little blurb shows my intent that the masks should be 0xfffffffful.
It's not like you don't make typos.

Quote:
>  If unsigned long is > 32 bits, then the technique presented above
>truncates the upper bits.

No shit, Sherlock! The whole intent here is to do arithmetic modulo
32 bits in a portable manner, not to take advantage of the implementation's
full unsigned long precision. Hence the masks. If I wished to take
advantage of the full precision, I would have coded it differently.

Either way it's portable ANSI C.

Quote:

>: I would tailor the routine to your particular needs.

>  I recommending finding code that works.

I do too, because it surely won't emerge from among Scott Nudd's constructive
criticisms.

Still, it serves me right to be chastized for posting untested code.
I apologize to the original poster for the incorrect constants.



Sun, 10 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word


Quote:



>:   More non-functional code from Kylheku.
>:   Kylheku assumes unsigned long has a size of 32 bits.

>Ok, he could go to limits.h and improve that.  Try finding limits.h in
>your assembler, moron.

Whether that would be an improvement is a matter of opinion and depends
on as of yet unstated requirements. A strictly conforming program need
not take advantage of precisions beyond the minimum limits.
There is no assumption in the code that unsigned long has a size of 32
bits, only that it has at least 32 bits. That's why the mask operations
to ensure arithmetic modulo 2^32 rather than modulo ULONG_MAX + 1.

Quote:
>:   His technique fails for negative numbers.

>It also fails depending on the endianness of the machine.  This sort of
>thing is why libraries to perform such tasks are written that have the
>same interface across platforms, and this same sort of thing is why
>no assembler will ever be 'portable.'

That is absolutely false. There is no endianness dependency in the function
at all. How could such a dependency arise, when only abstract operations
(shifts and bitwise logical operators) are used? Endianness and representation
issues arise when an integral object is accesseed in terms of its individual
bytes of storage, a dubious programming practice that was not used in my
example. It _is_ assumed, however, that a[0] is the least significant word,
hence the left shift moves in the direction a[0] -> a[1] -> ...


Sun, 10 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

Quote:



> > >   Kylheku assumes unsigned long has a size of 32 bits.
> >So what?
> > >   Kylheku also "ands" by an improper value in the line containing the
> > >   shift right.
> >What is improper with 0xffffffful, considering the assumption?

> Because it should be 0xfffffffful---the intended effect is to reduce the
> value modulo 2^32. Indeed, Scott Nudds has applied himself well. I'm surprised
> he caught the errors.

Actually, it shows why the gentleman is upset with C!
Here he is, with fine tuned skills which are of great
use in assembly but of much less use in C.  (Never mind
other languages which are a little more abstract than C.)

No wonder he would like the world to work in assembler.
A nice form of assembler, with all good things, such as
portability, readability, apple-pie... thrown in.  As long
as it is assembler -- which to Scott Nudds, means some environment
where his abilities such as being able to read hexadecimal
well and being able to find typos and wrong offset numbers easily,
have significant meaning and are appreciated.

Maybe if the skills of programming were being replaced with
the skills of giving commands to robots -- many others
of us would feel the same way and plead desperately
to continue the old ways, in the face of common sense.
(I sure hope if this comes about, we fare better than
that.)



Sun, 10 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

Quote:


> : >   Kylheku assumes unsigned long has a size of 32 bits.


> : Kaz was never challenged to write a portable version of this.

>   C pushers constantly write non-portable code while proclaiming to the
> world that C is portable.

>   They misrepresent reality in order to promote their religion.

Here again, rather than admit your failure, you resort to insulting and
re-iterating your mindless tripe.

Quote:


> : Your "portable assembler" has no predefined word size then?

>   It does.  Implementation provides security and portability.

What's the word size, then? 32 bits?
Then it will never be able to run on 64 bit machines.

The code Kaz has posted was never meant to be portable.
It is indeed possible to write non-portable code in C.
Whoever denies this, is indeed a "C pusher".

However, it is possible to write portable code in C and one could even
re-write Kaz' code to be portable to 64 bits and beyond:

# include       <sys/param.h>
void shift_left(unsigned long a[], int n, int shift, int do_rotate)
{
  unsigned long carry_in = 0, carry_out;
  int i;

  for (i = 0; i < n; i++) {
!       carry_out = (a[i] & 0xffffffful) >> (32 - shift);
     carry_out = a[i] >> (NBBY * sizeof(unsigned long) - shift);
!       a[i] = ((a[i] << shift) | carry_in) & 0xfffffful;
     a[i] = (a[i] << shift) | carry_in;
     carry_in = carry_out;
  }

  if (do_rotate)
     a[0] |= carry_out;

Quote:
}

(The lines marked with a '!' are the original lines)

NOTES
Now this code still doesn't work if n exceeds the size of an unsigned
long, but that's an entirely different problem.
Also, the code doesn't have comments, but that too, is not the issue
here.
By referring to the number of bits per byte by using NBBY (defined in
sys/types.h), the code even works for systems that don't have 8 bits per
byte! But even if that is not requested (after all, there are not much
left), NBBY can be recognized to mean "Number of Bits per BYte", much
better than the constant "8".



Mon, 11 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

:  >   Kylheku assumes unsigned long has a size of 32 bits.

: So what?

  It may not be the case.

:  >   Kylheku also "ands" by an improper value in the line containing the
:  >   shift right.

: What is improper with 0xffffffful, considering the assumption?

  The assumption that is wrong, along with the mask.

:  >   Similarly her "ands" by an improper value in the line containing the
:  >   shift left.

: What is improper with 0xfffffful, considering the assumption?

  The assumption that is wrong, along with the mask.


:  > : I would tailor the routine to your particular needs.

:  >   I recommending finding code that works.

: Why not provide it?

  I prefer avoiding bastard languages like C.

--
<---->



Mon, 11 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word

: As long
: as it is assembler -- which to Scott Nudds, means some environment
: where his abilities such as being able to read hexadecimal
: well and being able to find typos and wrong offset numbers easily,
: have significant meaning and are appreciated.

  M. Prasad's attempt to psychoanalyze miss the mark.  My primary
interest is code generation efficiency.  My secondary interest is
readability.  My next highest interest is the promotion of a secure
programming environment - which includes #2 as a component.

  Given a high level language that adequately addressed these concerns,
there would no longer be a need for assembler.

  C is a spectacular failure in all three areas.  It is one of the worst
languages ever created.

--
<---->



Thu, 14 Oct 1999 03:00:00 GMT  
 Help: bitwise operations on a 56 bit word



: >Ok, he could go to limits.h and improve that.  Try finding limits.h in
: >your assembler, moron.

: Whether that would be an improvement is a matter of opinion and depends
: on as of yet unstated requirements. A strictly conforming program need
: not take advantage of precisions beyond the minimum limits.
: There is no assumption in the code that unsigned long has a size of 32
: bits, only that it has at least 32 bits. That's why the mask operations
: to ensure arithmetic modulo 2^32 rather than modulo ULONG_MAX + 1.

Ok, but is there anything lost in using ULONG_MAX?  I don't have the code
in front of me and don't remember the reason for writing it, but I can't
think why you _wouldn't_ do it.

: >:   His technique fails for negative numbers.
: >
: >It also fails depending on the endianness of the machine.  This sort of
: >thing is why libraries to perform such tasks are written that have the
: >same interface across platforms, and this same sort of thing is why
: >no assembler will ever be 'portable.'

: That is absolutely false. There is no endianness dependency in the function
: at all. How could such a dependency arise, when only abstract operations
: (shifts and bitwise logical operators) are used? Endianness and representation
: issues arise when an integral object is accesseed in terms of its individual
: bytes of storage, a dubious programming practice that was not used in my
: example. It _is_ assumed, however, that a[0] is the least significant word,
: hence the left shift moves in the direction a[0] -> a[1] -> ...

My mistake.  I forgot that the C bitshift makes all machines look to be
big-endian.  Too long spent writing MIPS assembly for me:-)  I hardly
ever use the C bitshifts(should, but don't,) and so I tend to confuse
myself occasionally.

Later,

--
John J. Adelsberger III                 St. Louis, MO:  (314)434-3067  

"I'm the root of all that's evil, but you can call me Cookie."  - {*filter*}hound
                                                                  Gang



Thu, 14 Oct 1999 03:00:00 GMT  
 
 [ 32 post ]  Go to page: [1] [2] [3]

 Relevant Pages 

1. Help: bitwise operations on a 56 bit word

2. multiplier with 56 bit

3. error Logout 56, Help with

4. Doing bitwise AND operation in shell scripts

5. Bitwise operations

6. Bitwise Logical Operations?

7. bitwise operations

8. bitwise operations (try #2)

9. Question: Bitwise operations in Oberon

10. Bitwise operations on X's and Z's

11. Bitwise operations in Scheme

12. bitwise operation on 64 bits value, how?

 

 
Powered by phpBB® Forum Software