malat malat - 27 days ago 15
C Question

shifting a negative signed value is undefined

I am starring at the original JPEG standard (ITU 81), in particular the figure Figure F.12: extending the sign bit of a decoded value in V:

For reference the

SLL
terms means:
shift left logical operation
(see page 15 of the PDF)

Figure F.12: extend sign bit.

Now the famous libjpeg implementation decided to implement it this way (quite direct transcription):

/*
* Figure F.12: extend sign bit.
* On some machines, a shift and add will be faster than a table lookup.
*/

#ifdef AVOID_TABLES

#define HUFF_EXTEND(x,s) ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))

#else

#define HUFF_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))

static const int extend_test[16] = /* entry n is 2**(n-1) */
{ 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };

static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
{ 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };

#endif /* AVOID_TABLES */


Quite obviously shifting a negative signed value is UB, so I am wondering what the original author of the JPEG standard actually meant here. Is the JPEG standard limited to Two's complement number representation ?

Answer

Is the JPEG standard limited to Two's complement number representation ?

With the chart using SLL rather than *2, the flow chart is relying of 2's complement implementation.

C, OTOH, is not limited to 2's complement nor using shifts in a certain "2's complement" way. Better to code without that assumption. Using unsigned types is a good first step.

// ((-1)<<15) + 1
((-1u)<<15) + 1

Need to see applications of HUFF_EXTEND() for a deeper answer.

Comments