Negative of UInt8

Question

I have this code in Objective-C and I want to write it in Java. However there is the statement (-(crc & 1)) that gives me problems. After some googeling it seems that the negative of an unsigned is generally not well defined. I didn't quite understand it though. Maybe somebody who knows CRC can tell me what the equivalent in Java would be.

I need exactly an equivalent method as a device with this Objective-C code checks my calculated crc against its self calculated.

+ (UInt32) crc32:(UInt32) crc ofByte: (UInt8) byte
{
    int8_t i;
    crc = crc ^ byte;
    for (i = 7; i >= 0; i--)
    {
        crc = (crc >> 1) ^ (0xedb88320ul & (-(crc & 1)));
    }
    return(crc);
}

The solved code with help of comments. Seems like I searched the mistake in the wrong place.

private void addByteToCRC(byte oneByte) {
    crc ^= oneByte & 0xFF;
    for (int i = 7; i >= 0; i--)
    {
        crc = (crc >>> 1) ^ (0xedb88320 & (-(crc & 1)));
    }
}

Both checksums start of with a crc value of 0xFFFFFFFF.

"the negative of an unsigned is generally not well defined" - it is very well defined: An **unsigned** integer cannot be negative. That's the idea. — too honest for this site, Apr 03 '17 at 15:21
Yeah I understood that. So the question is what is the equivalent of what this program is actually doing. Because it is working. — findusl, Apr 03 '17 at 15:22
I am also happy if you just tell me what it does and I program it myself. — findusl, Apr 03 '17 at 15:24
The `-(crc & 1)` trick is used to XOR with 0xedb88320 only iff the bottom bit is set. The same thing works in Java. — harold, Apr 03 '17 at 15:24
Perhaps if you might need to learn about [two's complement](https://en.wikipedia.org/wiki/Two's_complement) (most common way to handle negative integers)? — Some programmer dude, Apr 03 '17 at 15:24
It most likely calcculates a CRC32. Now don't tell me you did not find information about that on the net. Btw: That is no C code. — too honest for this site, Apr 03 '17 at 15:26
I found information about CRC32 take a guess. And it even was commented what it should do but so tried with several libraries and it didn't work as it should. That's why I'm here... — findusl, Apr 03 '17 at 15:34
This works for two's complements only and indeed the standard does not require that integers are two's complements. (There are three options: sign+magnitude, two's complement or on's complement.) However, nearly all machines use two's complement. — Amin Negm-Awad, Apr 03 '17 at 17:59

score 1 · Answer 1 · edited May 23 '17 at 12:17

There are some differences between (Objective-)C and Java, but at a guess you may have identified the wrong problem. Java does not have unsigned integer types. However it does have bitwise operators which treat integers as just strings of bits, and later versions of Java do have unsigned operators which when applied to integers operate on the underlying bit patterns as though they represented unsigned values.

The expression crc & 1 will yield a result of 0 or 1 depending on whether crc was even or odd.

The expression -(crc & 1) therefore evaluates to 0 or -1. The bit pattern of 0 is all zeros and for -1 it is all ones - the latter is true in (Objective-)C regardless of the underlying representing of integers as 1's or 2's complement, see Is it safe to use -1 to set all bits to true? for an explanation.

The expression 0xedb88320ul & (-(crc & 1)) therefore evaluates to 0 or 0xedb88320.

The expression crc >> 1 is the logical, or unsigned, shift right in (Objective-)C as src is defined as unsigned (right shifts for signed integers are "implementation defined" in (Objective-)C).

The expression x ^ 0 for any x evaluates to x.

Put that all together and your whole expression (crc >> 1) ^ (0xedb88320ul & (-(crc & 1))) conditionally xors crc >> 1 with 0xedb88320 base don whether crc is odd or even.

Now you just need to reproduce the same behaviour in Java.

Java uses 32-bit 2's complement integers for int (JLS: Primitive Types and Values) and provides bitwise operators which treat them as just bit-strings.

The hexadecimal constant comes just 0xedb88320 and has int (32-bit) type.

The expression -(crc & 1) therefore evaluates as in (Objective-)C.

However the expression crc >> 1 will not evaluate the same as in (Objective-)C. In Java the >> is an arithmetic shift right, which replicates the sign-bit during the shift. This choice stems from Java using signed types. Fortunately Java also provides the >>> operator to perform a logical, or unsigned, right-shift.

So my guess is you may have identified the wrong problem in your conversion and you need to use the >>> operator.

HTH

score 1 · Accepted Answer · answered Apr 03 '17 at 21:53

The -(crc & 1) works fine, and is not your problem. What it does is to copy the low bit of crc to all of the bits, since in two's complement representation, –1 is all ones.

There are two things you need to fix for Java, which does not have unsigned integers. First is that the right shift needs to be a logical right shift, >>>. That avoids copying the sign bit when shifting down, and instead shifts in a zero bit. Second, you need to guard against a character being signed-extended to an int, so byte (which will need a different name in Java) needs to be anded with 0xff. So:

crc ^= octet & 0xff;

and

crc = (crc >>> 1) ^ (0xedb88320ul & (-(crc & 1)));

Negative of UInt8

2 Answers2