Shift 'em bits

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

Reply to
WaldemarIII
Loading thread data ...

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

Reply to
Hans Müller

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
 Click to see the full signature
Reply to
Tauno Voipio

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?

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

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

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

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;

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 n=63!

Paul Burke

Reply to
Paul Burke

"Tauno Voipio" schreef in bericht news:%Aknd.155$ snipped-for-privacy@read3.inet.fi...

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

Freescale HC08.

Metrowerks CodeWarrior V3.0 limited to 4kBytes code.

Alas, no such thing as assembler allowed, otherwise the thing would be trivial

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

Reply to
WaldemarIII

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.
 Click to see the full signature
Reply to
Stef

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?

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

Why?

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 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*.

Use ASM and forget it! :-/

--don

Reply to
Don

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

It appears not.

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
 Click to see the full signature
Reply to
Grant Edwards

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

Reply to
Guy Macon

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.

Reply to
Bryan Hackney

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

Reply to
Paul Keinanen

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

Reply to
Everett M. Greene

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

Reply to
Lewin A.R.W. Edwards

Assuming the hardware doesn't support it directly,

atomic?

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

Best regards, Spehro Pefhany

--
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
 Click to see the full signature
Reply to
Spehro Pefhany

"Spehro Pefhany" schreef in bericht news: snipped-for-privacy@4ax.com...

If, for some reason the interrupt are not allowed to be turned off, one could (perhaps) use another atomic operation to protect the results being processed.

For instance, if the interrupt supplies the 64 value that needs to be shifted, it can place these in a buffer.

The main loop increments an index (atomic) and starts working on the previously stored value.

But this is all guess work.

--
Thanks, Frank.
(remove 'x' and 'invalid' when replying by email)
Reply to
Frank Bemelman

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

Reply to
Paul Burke

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

Reply to
Lewin A.R.W. Edwards

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

Reply to
Toby Thain

Atomic 64 bit shift on an 8bit cpu ? You need to disable interrupts.

Out of curiostiy, why is assembly out of question ?

Maybe, it'll help you tell us what and why you shift. There is maybe a better way ?!

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
 Click to see the full signature
Reply to
42Bastian Schick

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.