Shift 'em bits

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hi

Is there an atomic way to shift 64 bits either left or right?
Shifting a double (8 bytes) doesn't work. Compiler won't
allow it. Embedded assembly is out of the question and
and a C function conating a loop shifting the individual
bytes consumes too much time.

Suggestions... Love to hear from you...

Waldemar



Re: Shift 'em bits
you could break it in two 32bit operations like

// shift 64 bits left
// assumes v1 holds lower 32bit of your 64 bit word, v2 the higher
v2 += v2 + (v1 & 0x80000000 > 0);
v1 += v1;

in v1 and v2 now is the left shifted result. v1 and v2 cold be a casted
pointer to your memory locations.

if your target mashine is a 32bit system this might be fast enough.
on a smaller one, you should you same assemble inline, it is much faster.

hth
Hanst

Re: Shift 'em bits
Quoted text here. Click to load it

double is a floating-point entity - shifting it is not sensible,
as the internal field boundaries will be broken if it is shifted
as a bit pattern.

Which processor?

Which compiler?

Is an external assembly module out of question?

If the compiler supports long long, it's the solution.

--

Tauno Voipio
tauno voipio (at) iki fi



Re: Shift 'em bits
Quoted text here. Click to load it
True, but I would expect to be able to screw around with
an intrinsic 8 byte variable any way I would feel like! Not
so... C defies its own philosophy...

Quoted text here. Click to load it
Freescale HC08.

Metrowerks CodeWarrior V3.0 limited to 4kBytes code.

Quoted text here. Click to load it
Alas, no such thing as assembler allowed, otherwise the
thing would be trivial

Quoted text here. Click to load it
CW does support long longs but looking at the disassembly
I get the strong impression that these are only 32 bits
in length. Am I wrong?

Waldemar



Re: Shift 'em bits
In comp.arch.embedded,
Quoted text here. Click to load it
Why look at the assembly for this when you can find it in the Fine
Manual? (RT)

(Metrowerks Compiler_HC08.pdf, page 527)

+--------------------+-------+-------------+------------+--------------------+
| Type               |Default| Default Value Range      | Formats Available  |
|                    |Format | Min         | Max        | With Option -T Min |
+--------------------+-------+-------------+------------+--------------------+
| signed long long   | 32bit | -2147483648 | 2147483647 | 8bit, 16bit, 32bit |
+--------------------+-------+-------------+------------+--------------------+
| unsigned long long | 32bit | 0           | 4294967295 | 8bit, 16bit, 32bit |
+--------------------+-------+-------------+------------+--------------------+


--
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

Love is being stupid together.
We've slightly trimmed the long signature. Click to see the full one.
Re: Shift 'em bits
stef33d@yahooI-N-V-A-L-I-D.com.invalid (Stef) writes:
Quoted text here. Click to load it

Strange (to say the least)!  Why bother to support the syntax
of longlong and then define it to be 32 bits?

Re: Shift 'em bits
Quoted text here. Click to load it


That's a strong hint that a truly "atomic" method doesn't exist, on
whatever target CPU you might be talking about.  Does your compiler
support 64-bit integers at all?

Quoted text here. Click to load it

Why would you restrict yourself artificially, like that?  Tools exist
to be *used*, not to be dismissed summarily as "out of the question".

Quoted text here. Click to load it

Why would you go all the way from 64 bits to individual bytes?  There
are several intermediate unit sizes in between (on most CPUs, at
least), which would make a lot of sense here.  E.g. the somewhat
obvious split into two 32-bit unsigned longs, for which the
right-shift by n would become:

    low_part = low_part >> n | high_part << (32 - n);
    high_part >>= n;

--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Shift 'em bits

Quoted text here. Click to load it

There's no atomic way to shift a 32-bit value on an HC08.

Quoted text here. Click to load it

It appears not.

Quoted text here. Click to load it

The HC08 is an 8-bit CPU. It supports a few 16 bit operations
(I don't remember if there is a 16-bit shift or not).  Using
two 32-bit variables will probably generate the fastest code,
but the OP really needs to try it and then look at the assembly
generated by the compiler to decided.

--
Grant Edwards                   grante             Yow!  I am covered with
                                  at               pure vegetable oil and I am
We've slightly trimmed the long signature. Click to see the full one.
Re: Shift 'em bits

Quoted text here. Click to load it

If you've no long long (or long long is less than 64 bits) you're out of
luck for a simple shift. You'll have to do something like:

long v[2];
...

void lshift64( long *v)
{
v[0] =(v[0]<<1) | ((v[1] & 0x80000000) ? 1 : 0);
v[1] <<= 1;
}

void lshift64( long *v)
{
vl = (vl>>1) | ((vh & 1) ? 0x80000000 : 0);
vh >>= 1;

which isn't at all pretty. And I'll leave you to work out the masking
for n bit shifts. Perhaps faster but even nastier to have a whole set of
shift functions for n=1 to n63%!

Paul Burke

Re: Shift 'em bits
Quoted text here. Click to load it

You missed the word "atomic", which does not mean "fast".

Re: Shift 'em bits

Quoted text here. Click to load it

No, I didn't think that was what he really wanted, as the OP also said
that he couldn't afford the time for a bit-shifting loop. The answer to
"atomic" is simply, if there isn't a single instruction that does a 64
bit n shifts left or right, and he can't turn off interrupts, tough.

Paul Burke


Re: Shift 'em bits
Quoted text here. Click to load it

OIC. Well, if the OP is going to treat words like Humpty Dumpty... I'll
just pretend I never posted to this thread :)



Re: Shift 'em bits



Quoted text here. Click to load it

For the sake of discussion, could someone comment this
seriously non-portable code (works with gcc on intel):

typedef unsigned int    thirtytwo;
typedef struct {
   thirtytwo    but:31;
   thirtytwo    bit:1;
}  msbsliced;
typedef struct {
   thirtytwo    bit:1;
   thirtytwo    but:31;
}  lsbsliced;
typedef thirtytwo unsliced;
typedef union {
   unsliced    all;
   msbsliced    msb;
   lsbsliced    lsb;
} sliced;
typedef struct {
   sliced high;
   sliced low;
}    sixtyfour;


void
shl (
   sixtyfour *pdata
) {
   pdata->high.lsb.but=pdata->high.msb.but;
   pdata->high.lsb.bit=pdata->low.msb.bit;
   pdata->low.lsb.but=pdata->low.msb.but;
   pdata->low.lsb.bit=0;
}




Re: Shift 'em bits


Quoted text here. Click to load it


While we're writing long delayed follow-ups, let me point out a
nitpick: the above absolutely has to be changed to unsigned.
Otherwise hell will break loose.

Quoted text here. Click to load it

I still think

    void lshift64(unsigned long *v)
        {
       v[0] = (v[0] << 1) | (v[1] >> 31);
       v[1] = v[1] << 1;
    }

is easier to read than that --- it may even be more efficient in
implementation, too.

Quoted text here. Click to load it

No.  This isn't just seriously non-portable, it's nonsensical.
There's nothing to be gained from discussing the finer points of what
is, for all important means and purposes, pure voodoo.  That routine
might just as well be called 'abakadabra'.

--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Shift 'em bits
Quoted text here. Click to load it

Do you truly mean "atomic"?  (i.e. an operation whose intermediate
results can NEVER be seen -- AS IF uninterruptible)  Or, do you
just mean something that you can write in a simple C expression?

Quoted text here. Click to load it

The language won't allow it.  Shift operators only apply to integer
data types (int, short, char, etc.)

And, if you were expecting to cast some "random" group of 64 contiguous
bits to a double, they might get *altered* in the process (since not all
groups of 64 bits represent valid doubles -- assuming your doubles *are*
64 bits!)

Quoted text here. Click to load it

Why?

Quoted text here. Click to load it

Also, there be dragons there.  If you are presumably aspiring to
write portable code (hence the reason you rule out embedded
assembly), you have to be very careful about how you have
defined that "64 bit datum" (if, in fact, it *is* a 64 bit datum!)
E.g., char's aren't *guaranteed* to be 8 bits (read the standard
or argue the point with a language guru) -- though, chances are, your
compiler treats them as such.

But, you might find that you have defined an "8 uchar array" as your
"64 bit datum", yet, you try to manipulate it as a "2 ulong array".
Does your compiler ensure that char arrays are aligned in a manner
compatible with the alignment it (or the CPU!) expects for *longs*?

You also have to be wary of any right shift operations since
the language gives no assurances as to *what* gets shifted in
from the left.

Etc.

If you really are trying to write portable code (avoiding ASM for
some reason), use the manifest constants in <limits.h> and
conditionally chose the widest UNSIGNED data type you can.
Define your "64 bit datum" as an array of those and build
"monitors" to manipulate data of this (64 bit) type -- i.e. pretend
you are dealing with *objects*.

Quoted text here. Click to load it

Use ASM and forget it!  :-/

--don



Re: Shift 'em bits


Quoted text here. Click to load it

I want to remove a screw and a screwdriver is out
of the question.  What sort of hammer should I use?


Re: Shift 'em bits
Quoted text here. Click to load it

If you don't have a 64 bit data type, why do you need to shift
64 bits? It sounds like you want an arbitrary bit shifter, by
which 64 bits might be a place to start.

I think you picked the wrong processor given your constraints.

Re: Shift 'em bits
On Fri, 19 Nov 2004 11:20:46 +0100, "WaldemarIII"


Quoted text here. Click to load it

No atomic way if the hardware does not support 64 bit values.

Do you need to shift the 64 bit quantity multiple positions to the
left or right or just a single position ?

For multiple bit shifts, declare an 8 byte array overlapping the 64
bit value. For a little endian architecture, shifting the value 8 bits
left is just

for (i=7 ; i > 0 ; i--) Bytes[i]= Bytes[i-1] ; Bytes[0] = 0 ;

In similar way, you can do 16, 24, 32, 40, 48 and 56 bits left or
right shifts simply by a byte copy.  

To make say a 19 bit shift right, first shift 16 bits right by byte
copying and then perform a 3 bit right shift by a bit by bit shifting.
To do a 23 bit right shift, perform 24 bit right shift by copying and
a one bit left shift. You need a 9 byte workspace for this.

Since you do not have access to the carry bit in C, doing the required
1-4 bit shift right or left, it is easiest to handle one byte at a
time. For each byte, you need two multibit shifts (which may be
available even in simple processors) and one OR operation.

In addition you may need to copy each byte 1-7 bytes left or right for
the multiples of 8 bit shifting.

With an architecture capable of multibit shifting on a single byte and
some autoincrementing pointers, you might be able to handle a single
byte with perhaps 10-12 instruction, thus a 8 byte (64 bit) value
could be shifted 1-64 bits left or right in about 80-100 instructions.
To be effective, you need 7-9 hard coded paths for the 0-4 bit right
_and_ left shifts.

To be portable, you also need to evaluate the situation for big endian
processors.

Paul
          

Re: Shift 'em bits
Quoted text here. Click to load it

Whether any copying is necessary depends on how the shifted value is
going to be accessed later. For instance, if the shifts are multiples
of 8, don't copy anything, simply adjust a byte index (and when access
is required, use it modulo 8, in this case). Call it lazy shifting
(actually a rotate).

The same applies if the shifts are not multiples of 8; use a bit
index, and the accessing operation will involve a shift and mask. IMHO
the most efficient way of recording the "shift" hinges on what happens
to the data later... which has not been elaborated, except that the OP
says copying bytes is too slow. Which to me, suggests a "lazy"
approach.

--Toby

Quoted text here. Click to load it

Re: Shift 'em bits
On Fri, 19 Nov 2004 11:20:46 +0100, the renowned "WaldemarIII"

Quoted text here. Click to load it

Assuming the hardware doesn't support it directly,

atomic?

<turn off interrupts>
<some C, assembly or other stuff>
<restore original interrupt setting>

Quoted text here. Click to load it

Others have made reasonable suggestions on the "stuff" part.


Best regards,
Spehro Pefhany
--
"it's the network..."                          "The Journey is the reward"
snipped-for-privacy@interlog.com             Info for manufacturers: http://www.trexon.com
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline