Board index » delphi » Shifting bits in bytes/words/longs...

Shifting bits in bytes/words/longs...

Hi,

I have a problem which boils down to needing to shift all the bits in a
hunk of memory by an arbitrary number of bits.

The approach I initially took was to move the memory to the closest byte
using move() and then to run through that memory 4 bytes (an integer) at
a time and shift those 4 bytes by the appropriate number of bits and add
on the necessary bits from the adjacent 4 byte chunk to fill in the gap.
However, the results are a bit 'weird' and the only thing I can think of
is that somehow the endianess of the machine is playing tricks.

To narrow down the problem I reduced it to simply shifting each 4 byte
chunk and not adding in the extra bits. What appears to be happening is
that each byte in the 4 byte integer is shifted by the number of bits,
rather than the 4 byte integer as a whole.

To be more precise, the block of memory contains a sequence of bits
forming black and white pixels in an image. When applying the shifting
(for example shift right by 2) to sucessive 4 byte integers along this
memory block, each byte is shifted by 2 bits and the 'exposed' bits
appear to inherit the leftmost two bits of a byte either 1 or 2 bytes
adjacent to it. I can only get this to work if I apply the shifting on a
byte by byte basis. Attempting to use words or integers just messes it
up :-(

Does anyone have nny suggestions on how to do this in 4 byte chunks (its
much faster)? Or am I stuck with doing it in 1 byte chunks (slow)?

TIA,

Raymond.

--
Raymond Wilson

 

Re:Shifting bits in bytes/words/longs...


Quote
Raymond Wilson wrote:

> Hi,

> I have a problem ....

> Raymond.

> --
> Raymond Wilson

Shifting words and longwords cause problems because of the byte order on
the Intel processors
E.g. Word : lowbyte, highbyte
thus bit order is: 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8
So shifting does not work!
With longwords it's the same.
You could use an lookup table or stay with the byte shift this works
allways!

Ben

Re:Shifting bits in bytes/words/longs...


In article <31F5CC4D.4...@chem.leidenuniv.nl>, ben
<cea_...@chem.leidenuniv.nl> writes

Quote
>Shifting words and longwords cause problems because of the byte order on
>the Intel processors
>E.g. Word : lowbyte, highbyte
>thus bit order is: 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8
>So shifting does not work!
>With longwords it's the same.
>You could use an lookup table or stay with the byte shift this works
>allways!

I had feared as much! This raises two issues:

1. How does Delphi efficiently implement X SHR 2 where X is of type WORD
or INTEGER?

AND

2. When I write the following code, is this why I get the same problem:

Procedure ShiftMe(P : Pointer);
{ Shift 4 bytes pointed to by P left by 2 bits. P is pointer to memory
block which is an array of bytes }

var
  t : array[1..4] of byte; { Array of bytes to confound Endians!}

begin
  move(P^, t, 4);
  asm
    mov edx, t
    shr t, 2
    mov t, edx
  end;
  move(t, p^, 4);
end;

--
Raymond Wilson

Re:Shifting bits in bytes/words/longs...


Quote
In article <pakGLCADuJ9xE...@mcgltd.demon.co.uk> Raymond Wilson <su...@mcgltd.demon.co.uk> writes:
>From: Raymond Wilson <su...@mcgltd.demon.co.uk>
>Subject: Shifting bits in bytes/words/longs...
>Date: Tue, 23 Jul 1996 10:29:39 +0100
>Hi,
>I have a problem which boils down to needing to shift all the bits in a
>hunk of memory by an arbitrary number of bits.
>The approach I initially took was to move the memory to the closest byte
>using move() and then to run through that memory 4 bytes (an integer) at
>a time and shift those 4 bytes by the appropriate number of bits and add
>on the necessary bits from the adjacent 4 byte chunk to fill in the gap.
>However, the results are a bit 'weird' and the only thing I can think of
>is that somehow the endianess of the machine is playing tricks.
>To narrow down the problem I reduced it to simply shifting each 4 byte
>chunk and not adding in the extra bits. What appears to be happening is
>that each byte in the 4 byte integer is shifted by the number of bits,
>rather than the 4 byte integer as a whole.
>To be more precise, the block of memory contains a sequence of bits
>forming black and white pixels in an image. When applying the shifting
>(for example shift right by 2) to sucessive 4 byte integers along this
>memory block, each byte is shifted by 2 bits and the 'exposed' bits
>appear to inherit the leftmost two bits of a byte either 1 or 2 bytes
>adjacent to it. I can only get this to work if I apply the shifting on a
>byte by byte basis. Attempting to use words or integers just messes it
>up :-(
>Does anyone have nny suggestions on how to do this in 4 byte chunks (its
>much faster)? Or am I stuck with doing it in 1 byte chunks (slow)?
>TIA,
>Raymond.
>--
>Raymond Wilson

Raymond:

I'm curious how you are doing it.  I'm not really into this, but looked up
bitwise operators in the help file.  There are some operators that appear to
do this for you.  Also, you can build a case record type that might help.  I'm
probably not using the right terms here, so let me give an example (though
it's not complete.  I haven't played with this for a few years, so the syntax
may not be right, but the idea works!))

procedure move_them;
var
  something: record case boolean of
     1:  (x:array [0..100] of integer;
        xf: integer);
    2: (yf: integer;
        y: array [0..100] of integer);
    end;
  hold: array [0..100] of integer;

begin
  move (something.x,hold,101);       {move it to the hold}
  move (hold,something.y,101);       {move it back in but offset by 1}
  something.yf := 0;                          {set the leading integer value}
end;

Hopefully, this give you the idea, more or less.  Of course, I may not have
understood the problem to begin with either!
-Dave

Re:Shifting bits in bytes/words/longs...


In article <krajcard.11.31F68...@ohsu.edu>, krajc...@ohsu.edu writes

Quote
>>Does anyone have nny suggestions on how to do this in 4 byte chunks (its
>>much faster)? Or am I stuck with doing it in 1 byte chunks (slow)?

>Raymond:

>I'm curious how you are doing it.  I'm not really into this, but looked up
>bitwise operators in the help file.  There are some operators that appear to
>do this for you.  Also, you can build a case record type that might help.  I'm
>probably not using the right terms here, so let me give an example (though
>it's not complete.  I haven't played with this for a few years, so the syntax
>may not be right, but the idea works!))

>procedure move_them;
>var
>  something: record case boolean of
>     1:  (x:array [0..100] of integer;
>        xf: integer);
>    2: (yf: integer;
>        y: array [0..100] of integer);
>    end;
>  hold: array [0..100] of integer;

>begin
>  move (something.x,hold,101);       {move it to the hold}
>  move (hold,something.y,101);       {move it back in but offset by 1}
>  something.yf := 0;                          {set the leading integer value}
>end;

>Hopefully, this give you the idea, more or less.  Of course, I may not have
>understood the problem to begin with either!

This works fine if you want to shift by a multiple of 16 bits.
Unfortunately I need to shift by an arbitrary number of bits (eg: 17
bits). I do actually use a very similar approach to by moving the block
so that all of the bits are < 8 bits away from their correct location.
The second phase involves moving through the block and using SHL/SHR
operations move the bits to their correct location. e.g. shift them left
by shift bits:

type
  double_byte_array : array[1..2] of byte; // I want this to be Integer,
                                           // as its 4 timnes faster.
var
  p : Pointer; // Points to memory to shift by < 8 bits
  x : ^double_byte_array;

...

for i := 1 to num_to_do do
  begin
    x := double_byte_array(P);
    x^[1] := (x^[1] SHL Shift) OR (x^[2] SHR (8 - shift));
    inc(p);
  end;

...

Another kind soul has suggested using multiply/divide instead of
SHL/SHR. Perhaps this is the way Delphi implements SHL/SHR?

Raymond.
--
Raymond Wilson

Other Threads