New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Debug safety: shifting by >= bit width #403

Closed
andrewrk opened this Issue Jul 5, 2017 · 7 comments

Comments

Projects
None yet
2 participants
@andrewrk
Member

andrewrk commented Jul 5, 2017

In C, x << y or x >> y where y is >= bit width of x is undefined behavior. It should also be the case in zig, with appropriate debug safety.

@andrewrk andrewrk added this to the 0.1.0 milestone Jul 5, 2017

@andrewrk andrewrk added the enhancement label Jul 5, 2017

@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Jul 6, 2017

Member

It might make sense to allow shifting right by a number == bit width. This would be equivalent to assigning to zero.

Member

andrewrk commented Jul 6, 2017

It might make sense to allow shifting right by a number == bit width. This would be equivalent to assigning to zero.

@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Aug 16, 2017

Member

The decision is to have the type of the right hand side be an integer with a log2 bit count of the left hand side.

So if shifting a u32, the type of right hand side is u5.

There's an issue when the left hand side is a non-power-of-2 integer type, such as u31. I suppose for these situations we can insert a debug safety check. It should be very rare in practice.

Member

andrewrk commented Aug 16, 2017

The decision is to have the type of the right hand side be an integer with a log2 bit count of the left hand side.

So if shifting a u32, the type of right hand side is u5.

There's an issue when the left hand side is a non-power-of-2 integer type, such as u31. I suppose for these situations we can insert a debug safety check. It should be very rare in practice.

@andrewrk andrewrk added the breaking label Aug 16, 2017

@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Aug 19, 2017

Member

Due to this issue, I'm adding these primitive types:

  • u3 (for shifting u8) (and i3 for consistency)
  • u4 (for shifting u16) (and i4 for consistency)
  • u5 (for shifting u32) (and i5 for consistency)
  • u6 (for shifting u64) (and i6 for consistency)
  • u7 (for shifting u128) (and i7 for consistency)
Member

andrewrk commented Aug 19, 2017

Due to this issue, I'm adding these primitive types:

  • u3 (for shifting u8) (and i3 for consistency)
  • u4 (for shifting u16) (and i4 for consistency)
  • u5 (for shifting u32) (and i5 for consistency)
  • u6 (for shifting u64) (and i6 for consistency)
  • u7 (for shifting u128) (and i7 for consistency)

@andrewrk andrewrk closed this in 9877687 Aug 19, 2017

@tiehuis

This comment has been minimized.

Show comment
Hide comment
@tiehuis

tiehuis Sep 30, 2017

Member

Having to shift with by a number == bit width has come up a fair few times in code I've been writing.

For example the following will get a compile error.

const T = @typeOf(a);
const b = a << Log2Int(a)(T.bit_count - offset)

The current workaround is simply to separate the cases for possibly larger shifts.

const T = @typeOf(a);
const b = if (offset == 0) {
    0
} else {
    a << Log2Int(a)(T.bit_count - offset)
}

This is a little ugly, and unfortunately we can't really seem to get around this without changing the types allowed as shift arguments (which is a nice solution in general for all other values).

I don't think the default should be changed, but a possible alternative could be to add an extra shiftLeftWide which takes a T as a shift value instead. Anyway, a minor right now. This is mainly a note that this case comes up in practice ocassionally.

Member

tiehuis commented Sep 30, 2017

Having to shift with by a number == bit width has come up a fair few times in code I've been writing.

For example the following will get a compile error.

const T = @typeOf(a);
const b = a << Log2Int(a)(T.bit_count - offset)

The current workaround is simply to separate the cases for possibly larger shifts.

const T = @typeOf(a);
const b = if (offset == 0) {
    0
} else {
    a << Log2Int(a)(T.bit_count - offset)
}

This is a little ugly, and unfortunately we can't really seem to get around this without changing the types allowed as shift arguments (which is a nice solution in general for all other values).

I don't think the default should be changed, but a possible alternative could be to add an extra shiftLeftWide which takes a T as a shift value instead. Anyway, a minor right now. This is mainly a note that this case comes up in practice ocassionally.

@andrewrk andrewrk modified the milestones: 0.1.0, 0.2.0 Oct 1, 2017

@andrewrk andrewrk reopened this Oct 1, 2017

@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Oct 1, 2017

Member

That's interesting. I think this is evidence that this safety is really important, because that ugly if statement is what you have to do to avoid undefined behavior. If we added a builtin function @shlWide it would just contain exactly the logic above, since the LLVM shift operation has undefined behavior for shifting >= number of bits of the integer.

Maybe this can simply be in the standard library?

@import("std").math.shl

we currently have:

error Overflow;
pub fn shl(comptime T: type, a: T, shift_amt: Log2Int(T)) -> %T {
    var answer: T = undefined;
    if (@shlWithOverflow(T, a, shift_amt, &answer)) error.Overflow else answer
}

we could introduce:

/// Shifts left. Overflowed bits are truncated.
/// A signed shift amount results in a right shift by that many bits.
pub fn shlTrunc(comptime T: type, a: T, shift_amt: var) -> T {
    const abs_shift_amt = absCast(shift_amt);
    const casted_shift_amt = if (abs_shift_amt >= T.bit_count) return 0 else Log2Int(abs_shift_amt);

    if (T.is_signed) {
        if (shift_amt >= 0) {
            return a << casted_shift_amt;
        } else {
            return a >> casted_shift_amt;
        }
    }

    return a << casted_shift_amt;
}
Member

andrewrk commented Oct 1, 2017

That's interesting. I think this is evidence that this safety is really important, because that ugly if statement is what you have to do to avoid undefined behavior. If we added a builtin function @shlWide it would just contain exactly the logic above, since the LLVM shift operation has undefined behavior for shifting >= number of bits of the integer.

Maybe this can simply be in the standard library?

@import("std").math.shl

we currently have:

error Overflow;
pub fn shl(comptime T: type, a: T, shift_amt: Log2Int(T)) -> %T {
    var answer: T = undefined;
    if (@shlWithOverflow(T, a, shift_amt, &answer)) error.Overflow else answer
}

we could introduce:

/// Shifts left. Overflowed bits are truncated.
/// A signed shift amount results in a right shift by that many bits.
pub fn shlTrunc(comptime T: type, a: T, shift_amt: var) -> T {
    const abs_shift_amt = absCast(shift_amt);
    const casted_shift_amt = if (abs_shift_amt >= T.bit_count) return 0 else Log2Int(abs_shift_amt);

    if (T.is_signed) {
        if (shift_amt >= 0) {
            return a << casted_shift_amt;
        } else {
            return a >> casted_shift_amt;
        }
    }

    return a << casted_shift_amt;
}
@andrewrk

This comment has been minimized.

Show comment
Hide comment
@andrewrk

andrewrk Oct 1, 2017

Member

Actually now that << is truncating left shift, we should make what is above math.shlTrunc named math.shl, and math.shl rename to math.shlExact

Member

andrewrk commented Oct 1, 2017

Actually now that << is truncating left shift, we should make what is above math.shlTrunc named math.shl, and math.shl rename to math.shlExact

@tiehuis

This comment has been minimized.

Show comment
Hide comment
@tiehuis

tiehuis Oct 1, 2017

Member

That sounds good. shl not returning an error makes a bit more sense API-wise as well.

Member

tiehuis commented Oct 1, 2017

That sounds good. shl not returning an error makes a bit more sense API-wise as well.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment