如何"blend"两个值不溢出？

Question

考虑以下函数：

// Return a blended value of x and y:
//   blend(100, 200, 1, 1) -> 150
//   blend(100, 200, 2, 1) -> 133
uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  uint32_t big_parts_x = parts_x;
  uint32_t big_parts_y = parts_y;
  return (uint8_t) ((big_parts_x * x + big_parts_y * y) /
                    (big_parts_x + big_parts_y));
}

有没有办法让接近到适当的 return 值而不需要任何大于 uint8_t 的分配？通过执行两次除法，您可以轻松地将其分解（较少舍入）为两个 uint16_t 的加法。你能只用 uint8_t 吗？

Answer 1

Is there a way to get close to appropriate return values without requiring any allocations greater than uint8_t?

理论上是的：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  return lookup_table[x][y][parts_x][parts_y];
}

实际上，查找将花费 4 GiB 的 RAM table，因此这可能不是一个好主意。

除此之外，它取决于您所说的 "close" 的含义（"acceptable worst case error" 可以有多大）以及有效值的范围（特别是对于 parts_x 和 parts_y).

例如（如果 parts_x 和 parts_y 的范围仅为 1 到 15）：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
  uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

  return (x >> 4) * scaleX + (y >> 4) * scaleY;
}

当然在这种情况下"close"意味着：

混合 (100, 200, 1, 1) = 6*8 + 12*8 = 144（不是 150）
混合 (100, 200, 2, 1) = 6*10 + 12*5 = 120（不是 133）

请注意（通常）乘法是 "expanding"。我的意思是，如果 a 有 M 位范围并且 b 有 N 位范围，那么 a*b 将有 M+N 位范围。换句话说（使用全范围）以避免溢出 uint8_t * uint8_t = uint16_t。除法明显更差（例如为了避免精度损失，1/3需要无限位），一些精度损失是无法避免的，结果中的位数决定了多少精度损失，8位精度是"not much".

另请注意，对于某些情况，我可以通过为这些情况添加额外的代码来改进上面显示的简单示例。例如：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  if(parts_x < parts_y) {
     return blend(y, x, parts_y, parts_x);
  }
  // parts_x <= parts_y now

  if(parts_x == parts_y*2) {
      return 2*(x/3) + y/3;
  } else if(parts_x == parts_y*3) {
      return 3*(x/4) + y/4;
  } else if(parts_x == parts_y*4) {
      return 4*(x/5) + y/5;
  } else if(parts_x == parts_y*5) {
      return 5*(x/6) + y/6;
  } else if( (x > 16) && (y > 16) ){
      uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
      uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

      return (x * scaleX + y * scaleY) >> 4;
  } else {
      uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
      uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

      return (x >> 4) * scaleX + (y >> 4) * scaleY;
  }
}

当然，使用比 uint8_t 更大的东西要容易得多，也快得多，所以...

Answer 2

以下将在没有任何额外分配的情况下合并。
即使 int/unsigned 是 16 位也能工作。

return (uint8_t) ((1u*parts_x*x + 1u*parts_y*y) / (0u + parts_x + parts_y));

Answer 3

符合标准的 C 实现保证执行至少 16 位的算术运算。

C standard 的第 6.3.1.1p2 节指出：

The following may be used in an expression wherever an int or unsigned int may be used:

An object or expression with an integer type (other than int or unsigned int ) whose integer conversion rank is less than or equal to the rank of int and unsigned int .

A bit-field of type _Bool , int , signed int ,or unsigned int .

If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int ; otherwise, it is converted to an unsigned int . These are called the integer promotions. All other types are unchanged by the integer promotions.

E.1 节还指出 int 必须能够支持至少在 -32767 到 32767 范围内的值，而 unsigned int 必须至少支持 0 到 65535 范围内的值。

由于 uint8_t 的等级低于 int，因此当它是大多数运算符的主题时，前者总是会被提升为后者，包括 +、-、* 和 /。

鉴于此，您可以通过以下轻微修改安全地计算该值：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
    return ((1u*parts_x*x) / (parts_x + parts_y)) + ((1u*parts_y*y) / (parts_x + parts_y));
}

表达式 parts_x*x 和 parts_y*y 的最大值为 65025。这对于 16 位 int 但不是 16 位 unsigned int 来说太大了，因此每个乘以 1u 以强制将值转换为 unsigned int 按照第 6.3.1.8 节中指定的 通常算术转换 :

the integer promotions are performed on both operands. Then the following rules are applied to the promoted operands:

If both operands have the same type, then no further conversion is needed.

Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank is converted to the type of the operand with greater rank.

Otherwise, if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type.

另请注意，我们将每个部分分别除以总和。如果我们在除法之前先将两个部分相加，分子可能会超过 65535。通过先除法，这会使每个子表达式回到 uint8_t 的范围内。然后我们可以将再次位于 uint8_t.

范围内的两部分相加

所以上面的表达式在符合 C 标准的编译器上保证 return 正确准确的答案。

如何"blend"两个值不溢出？

How to "blend" two values without overflow?

c

algorithm

integer-overflow