未定义负号的移位 [英] shifting a negative signed value is undefined

问题描述

我主演原始的JPEG标准( ITU 81 )，尤其是图图F.12:在V中扩展已解码值的符号位:

作为参考，SLL术语表示:shift left logical operation(请参阅PDF第15页)

现在，著名的libjpeg实现决定采用以这种方式实现(非常直接转录):

/*
 * 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 */

很显然，将负符号值移动了UB，所以我想知道JPEG标准的原始作者在这里实际上意味着什么. JPEG标准是否仅限于二进制补码表示?

解决方案

JPEG标准是否仅限于二进制补码表示?

在图表使用SLL而不是*2的情况下，流程图依靠2的补码实现.

C，OTOH，不限于2的补码，也不以某种"2的补码"方式使用移位.如果没有这种假设，最好编写代码.使用无符号类型是一个很好的第一步.

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

需要查看HUFF_EXTEND()的应用程序才能获得更深的答案.

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)

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 ?

解决方案

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.

这篇关于未定义负号的移位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！