Как «смешать» два значения без переполнения?

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));
}

Есть ли способ закрыть для соответствующих возвращаемых значений, не требуя каких-либо выделений больше uint8_t?Вы можете разбить его (меньше округления) на сложение двух uint16_t, выполнив два деления.Вы можете сделать это только с uint8_t?

Answer 1

Приведенное ниже объединится без каких-либо дополнительных выделений.
Работает, даже если int/unsigned имеет значение 16 бит.

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

Answer 2

Соответствующая стандартам реализация C гарантирует выполнение арифметических операций как минимум с 16 битами.

В разделе 6.3.1.1p2 стандарта C указано:

Следующее может использоваться в выражении везде, где могут использоваться int или unsigned int:

• Объект или выражение с целочисленным типом (отличным от int или unsigned int) чей ранг целочисленного преобразования меньше или равен рангу int и unsigned int.
• Битовое поле типа _Bool, int, signed int или unsigned int.

Если int может представлять все значения исходного типа (как ограничено шириной для битового поля), значение преобразуется в int;в противном случае он преобразуется в unsigned int.Они называются целочисленными акциями .Все другие типы не изменяются целочисленными повышениями.

В разделе 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:

, для которых выполняются целочисленные повышенияоба операнда.Затем к продвигаемым операндам применяются следующие правила:

• Если оба операнда имеют одинаковый тип, дальнейшее преобразование не требуется.
• В противном случае, если оба операнда имеют целочисленные типы со знакомили оба имеют целочисленные типы без знака, операнд с типом ранга преобразования меньшего целого числа преобразуется в тип операнда с большим рангом.
• В противном случае, если операнд с целочисленным типом без знака имеет рангЕсли значение больше или равно значению типа другого операнда, то операнд с целочисленным типом со знаком преобразуется в тип операнда с целым типом без знака.

Примечаниетакже, что мы делим каждую часть на общую сумму отдельно.Если мы сначала добавим обе части перед делением, числитель может превысить 65535. Делая сначала разделение, это возвращает каждое подвыражение обратно в диапазон uint8_t.Затем мы можем добавить две части, которые снова будут в диапазоне uint8_t.

. Таким образом, приведенное выше выражение гарантированно вернет правильный точный ответ на компиляторе, который соответствует стандарту C.

Answer 3

Есть ли способ приблизиться к соответствующим возвращаемым значениям, не требуя каких-либо выделений, превышающих 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 ГБ ОЗУ для справочной таблицы, так что это, вероятно, не очень хорошая идея.

Кроме того, это зависит от того, что вы подразумеваете под «близко» (насколько велика «допустимая ошибка в худшем случае»)может быть) и какой диапазон значений действителен (особенно для 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;
}

Конечно, в этом случае «закрыть» означает:

• blend (100, 200, 1, 1) = 6 * 8 + 12 * 8 = 144 (не 150)
• blend (100, 200, 2, 1) = 6 * 10 + 12 * 5 = 120 (не 133)

Обратите внимание, что (в общем) умножение "расширяется».Я имею в виду, что если a имеет M битов диапазона, а b имеет N битов диапазона, то a*b будет иметь M + N битов диапазона.Другими словами (используя полный диапазон), чтобы избежать переполнения uint8_t * uint8_t = uint16_t.Деление значительно хуже (например, чтобы избежать потери точности, 1/3 требует бесконечных битов), некоторые потери точности невозможно избежать, количество битов в результате определяет, сколько потери точности, а 8 бит точности "не много".

Также обратите внимание, что простой пример, который я показал выше, может быть улучшен в некоторых случаях, добавив дополнительный код для этих случаев.Например:

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, поэтому ...