Opened 4 weeks ago

Last modified 3 weeks ago

#687 reopened defect

P1034 - Wrap around in scaling list coding

Reported by: bheng Owned by:
Priority: minor Milestone:
Component: spec Version: VVC D7 vE
Keywords: Cc: ksuehring, bbross, XiangLi, fbossen, jvet@…

Description

For scaling list coding, there seems to be a wraparound process missing for the nextCoef derivation.

Specifically, the nextCoef is an accumulation of delta values, which could be as small as -128 each time:

nextCoef += scaling_list_delta_coef[ id ][ i ]

There is no wrapping process here, so after accumulating a few coefficients, nextCoef could be a very large negative number.

ScalingList[id][i] is just set equal to nextCoef.

ScalingList[ id ][ i ] = nextCoef

The value of ScalingList[id][i] is added to the predicted value and modulo wrapped:

ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] + 256 ) % 256 ) (7-72)

The wrapping used here assumes that the (ScalingMatrixPred + ScalingList) sum is no smaller than -256. However, as shown above, ScalingList could be a very large negative value. That would require a modulo of a negative number, which is undefined in the spec.

For example, the sequence of coefficients [144, 16, 144, 16, 144, 16, ... ] in scan order, requires all scaling_list_delta_coef = -128. It's impossible to code this sequence without either creating a negative modulo situation above, or coding delta values outside the legal range [-128,127] (like VTM does).

Assuming it was not intended to make certain patterns of scaling lists impossible to encode, I believe the nextCoeff value should be wrapped to stay within [-128,127].

Also, there seems to be a left parenthesis missing in equation (7-72) above.

Change history (8)

comment:1 Changed 4 weeks ago by delagrangep

Good catch, I did not have in mind that % was not defined for negative numbers.
I suggest changing (7-72) to:

ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] ) & 255

and, for editorial consistency reason, change (7-71) to:

ScalingMatrixDCRec[ id − 14 ] = ( ScalingMatrixDCPred + scaling_list_dc_coef[ id − 14 ] ) & 255

Rationale: we just want 8-bit overflow, and cast the result to uint8.
Such operation in syntax (for nextCoef) would be redundant: it is implementation-specific whether numbers are allowed to grow, or overflow as either int8 or uint8.

comment:2 Changed 4 weeks ago by bbross

  • Resolution set to fixed
  • Status changed from new to closed

Thanks for reporting.

This will be fixed JVET-P2001-vD.

comment:3 Changed 4 weeks ago by bheng

Thanks for confirming the problem.

Is it clear in the text that the result of that "& 255" with a negative value will be unsigned (0-255) and not signed (-128 to 127)? Or would there need to be something additional in the text to implement the "cast to uint8" process?

comment:4 Changed 4 weeks ago by ochubach

Hello Brian, all.
Thank you for catching this point. Because the "&" operation is not defined for negative numbers, I am not sure whether there is sense in adding it into the spec, since it's not going to solve the problem and may confuse other experts who will be reading it. We had modulo operation for defining nextCoef in our old version of the spec, but then removed it, since, as it was mentioned, it is an intermediate value and we thought it can be an implementation issue whether to allow wrap around or not. How about putting modulo back: ScalingList[ id ][ i ] = (nextCoef +256)%256. Would that solve the problem? This would not require defining of undefined "&" for negative numbers

comment:5 Changed 4 weeks ago by bbross

  • Resolution fixed deleted
  • Status changed from closed to reopened

I'll re-open this ticket until we have a working solution.

comment:6 Changed 4 weeks ago by bbross

  • Version changed from VVC D7 vC to VVC D7 vE

comment:7 Changed 4 weeks ago by delagrangep

From the spec:

& Bit-wise "and". When operating on integer arguments, operates on a two's complement representation of the integer value. When operating on a binary argument that contains fewer bits than another argument, the shorter argument is extended by adding more significant bits equal to 0.

This means that it is defined for negative numbers, using two's complement representation (negative number 'val' represented as 2n + val, with n as big as needed, or n = representation bit depth)

My understanding is that this also means that the result is unsigned (otherwise we would need to define when the result is signed).
See for example:

  • Ref position for DMVR (8-438)
  • Bitstream conformance of mv for IBC (8.6.2.1)

In thoses examples, one operand is signed but the result is obviously unsigned.

Note: I think the result of >> and << keep the sign of first operand ('arithmetic' shift), but and/or/xor result is always unsigned. Well, actually I think thoses bit-wise operators result in a binary representation, and exact signed/unsigned integer interpretation is clarified by the context.
Thus, the bitwise operators may need some clarification, but the same definitions and same kind of examples are found in HEVC... and we survived. So maybe it is just fine as-is.

I then suggest either

  • change (7-71) et (7-72) with & 255 as above
  • or change (7-72) as follows:
    ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] + 8192 ) % 256

comment:8 Changed 3 weeks ago by bheng

Thank you delagrangep for clarifying. I agree with your reasoning. The output of the & operation must already be understood to be an unsigned integer, otherwise it would be broken in several other places (like computing fractional MV components).

The "& 255" solution is cleaner in my opinion. I'd suggest we go with that as was originally suggested, so we can get the problem fixed and close this ticket. I notice in draft vE it's been changed to "& 256" so it's somewhere in-between at the moment.

Will you provide a similar fix for the software as well (using & rather than %)?

Note: See TracTickets for help on using tickets.