Binary shifts

[pjot]

Hi,



1) I noticed the following behaviour:

Code Select Expand


> (set 'a (pow 2 16))
65536
> (println (>> a 31))
0
> (println (>> a 32))
65536

It seems that a 32 bit shift returns the original number again. Being used to the old 6502 bitrotations, I would expect the result would be '0' again. Or the bits would 'scroll' into the integer bytes starting from the left, preserving all bits. Or is this expected behaviour (not mentioned in the manual)?



2) The range for integer numbers is mentioned to be between -2,147,483,648 and +2,147,483,647. The manual says: 'Integers are 32 bit plus including sign bit. Valid integers are numbers between -2,147,483,648 and +2,147,483,647. Bigger numbers are truncated to one of the two limits.' (Paragraph 'Evaluation rules and data types').

Code Select Expand


> (set 'a (pow 2 32))
4294967296
> (set 'a (- (pow 2 32) 1))
2147483646
> (set 'a (sub (pow 2 32) 1))
4294967295

It appears that bigger numbers seem to be translated to doubles automagically...?



Peter

[newdep]

shifting 31 bits on an integer 0-65535 should be possible but I

see indeed some strange effects...? Looks like << >> are not rolling..

manual says "Integers up to 32 bits may be shifted up to 31 positions."



> (<< 65536 31)

0

> (<< 65535 31)

-2147483648

> (<< 65534 31)

0

> (<< 65533 31)

-2147483648

> (<< 65532 31)

0

> (<< 65531 31)

-2147483648

> (<< 65530 31)

0

> (>> 65536 31)

0

> (>> 65535 31)

0

> (>> 65534 31)

0

> (>> 65533 31)

0

> (>> 65532 31)

0

> (>> 65531 31)

0

>

[Lutz]

When you shift 65536 => 0x10000, you have the most signifiicant bit already on the 16th place and can only shift 15 times. Neither the left nor the right shift are supposed to roll, and only the right shift duplicates bit 31 (in the 32nd position).



<< is a Arithmetic Shift Left (or Logic Shift Left)



<< is a Arithmetic Shift Left



thay are not Rotating Shifts,



Lutz

[newdep]

I knew i was not (<< keawa 2) :-)

[pjot]

Hm ok... but how can I rotate bits in a float?

Code Select Expand


> (set 'a (pow 2 32))
4294967296
> (float? a)
true
> (set 'a (<< a 1))
-2
> (float? a)
nil


Binary operations convert the type of the variable to integer (e.g. the C long), which is expected.



Actually I would like to perform a binary operation on an 'unsigned int', e.g. the full 32 bits. How can I do that with newLisp? How can I make newLisp ignoring the sign bit?



Peter

[Lutz]

Yes, the (pow 2 32) will overflow to 2147483647 when passed to an operator taking integers.



The sign disapperas when displaying the number hexadecimal.



(format "%X" -1) => "FFFFFFFF"



There is no way to make the 'sign bit' go away, its a 32bit machine and the special treatmant of bit 32 is necessary to make Arithmetic work in the CPU. An Arithmetic Right shift is essentially a division by 2 which has to maintain the sign of the number. This way bit 32 gets duplicated in the Arithmetic Right shift.



Lutz

[pjot]

Too bad that I can't use the full 32 bits... I guess I have to split to 2x16 in order to emulate the 'unsigned long' in C.



Peter

[Lutz]

You still can use floats without the fractional part to go to unsigned numbers beyond 32 bit and you still can do 32bit unsigned add/subtract/multiply:



(format "%x" (+ 0x50000000 0x50000000)) => "a0000000"



And you still can pass newLISP integers in/out to/from  'C' functions taking or returning 32bit unsigned integers. What is it exactly you are trying to do?



Lutz

[pjot]

Well, the hex workaround does not work, since the format returns a string. I cannot shift the bits in this string.



I am trying to read binary char data (0-255) into a buffer, which is a 32 bit unsigned long. At every read I need to shift this buffer some spaces to the left, in order to create space for a new incoming char.



If there are still some bits left in the buffer, which shift to the highest byte, then this highest byte may not become signed, since it is still a value representing an unsigned char (but kept in the highest byte of a 4-byte long).



All this I am using for a compression program completely written in newLisp, using the LZW algorithm:



http://www.turtle.dds.nl/newlisp/lzw.lsp">http://www.turtle.dds.nl/newlisp/lzw.lsp



The problem is in the 'input_code' function at the top. The compression works, by the way. Still it takes 2 minutes to compress 500k of data on my pentium4. But the decompression suffers from this issue.



There is a nice small compressor in C which can be used freely here:



http://www.oberhumer.com/opensource/lzo/#minilzo">http://www.oberhumer.com/opensource/lzo/#minilzo



I already tried to embed it in newLisp (hint). :-)



Peter

[Lutz]

When I do:

Code Select Expand


creating a fie with bytes > 127
(write-file "junk" "127128128130")

> (open "junk" "read")
3
> (read-char 3)
127
> (read-char 3)
128
> (read-char 3)
128
> (read-char 3)
130

Bytes come in unsigned and you should be able to do:

Code Select Expand


> (open "junk" "r")
3
> (format "%X" (set 'int32 (set 'int32 (| (<< int32 8) (read-char 3)))))
"7F"
> (format "%X" (set 'int32 (set 'int32 (| (<< int32 8) (read-char 3)))))
"7F80"
> (format "%X" (set 'int32 (set 'int32 (| (<< int32 8) (read-char 3)))))
"7F8080"
> (format "%X" (set 'int32 (set 'int32 (| (<< int32 8) (read-char 3)))))
"7F808082"
>


Now I see you problem: before the next shift you have to isolate the left most octet and put it a new higher int downstream. Its ok with '7F' which can be shifted 24 bits to the right, but not with '80' where the sign bit is set and you cannot do an arithmetic  right shift without duplicating the sign bit.

Code Select Expand


; the problem
 (format "%X" (>> 0x80000000 24)) => "FFFFFF80"


But there is a solution, you could mask the sign bit with zero after shifting this way getting the Logical Shift you need:

Code Select Expand


(format "%X" (& 0xFF (>> 0x80000000 24))) => "80"

Lutz



PS: thanks for the hint ;), I will research this

[pjot]

Well great, your trick works! (Not so difficult after all, actually. It is stupid of me that I could not find this myself.)



This issue can be closed. :-)



The working version of the LZW compression and decompression is here:



http://www.turtle.dds.nl/newlisp/lzw.lsp">http://www.turtle.dds.nl/newlisp/lzw.lsp



I am still testing it. During this week the final optimized version will appear, and I will anounce it when ready.



Thanks a lot!



Peter