From 92497d7df4b61ee62acfdd58bfb98569ff67214e Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Thu, 23 Aug 2018 11:01:52 -0700 Subject: Fix isRoundingError --- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 27 ++++++++++++++-------- 1 file changed, 17 insertions(+), 10 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index fa09da6ac..146bb9943 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -46,7 +46,7 @@ contract LibMath is return partialAmount; } - /// @dev Checks if rounding error > 0.1%. + /// @dev Checks if rounding error >= 0.1%. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. @@ -60,16 +60,23 @@ contract LibMath is pure returns (bool isError) { + // The absolute rounding error is the difference between the rounded + // value and the ideal value. The relative rounding error is the + // absolute rounding error divided by the absolute value of the + // ideal value. We want the relative rounding error to be strictly less + // than 0.1%. + // Let's call `numerator * target % denominator` the remainder. + // The ideal value is `numerator * target / denominator`. + // The absolute error is `remainder / denominator`. + // The relative error is `remainder / numerator * target`. + // We want the relative error less than 1 / 1000: + // remainder / numerator * denominator < 1 / 1000 + // or equivalently: + // 1000 * remainder < numerator * target + // so we have a rounding error iff: + // 1000 * remainder >= numerator * target uint256 remainder = mulmod(target, numerator, denominator); - if (remainder == 0) { - return false; // No rounding error. - } - - uint256 errPercentageTimes1000000 = safeDiv( - safeMul(remainder, 1000000), - safeMul(numerator, target) - ); - isError = errPercentageTimes1000000 > 1000; + isError = safeMul(1000, remainder) >= safeMul(numerator, target); return isError; } } -- cgit From e68942ee78eb19c27a96fb0b6b8b05c83b647bcc Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Thu, 23 Aug 2018 12:54:39 -0700 Subject: Handle zero case --- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 146bb9943..758b7ec90 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -60,14 +60,26 @@ contract LibMath is pure returns (bool isError) { + require(denominator > 0, "DIVISION_BY_ZERO"); + // The absolute rounding error is the difference between the rounded // value and the ideal value. The relative rounding error is the // absolute rounding error divided by the absolute value of the - // ideal value. We want the relative rounding error to be strictly less - // than 0.1%. - // Let's call `numerator * target % denominator` the remainder. + // ideal value. This is undefined when the ideal value is zero. + // // The ideal value is `numerator * target / denominator`. + // Let's call `numerator * target % denominator` the remainder. // The absolute error is `remainder / denominator`. + // + // When the ideal value is zero, we require the absolute error to + // be zero. Fortunately, this is always the case. The ideal value is + // zero iff `numerator == 0` and/or `target == 0`. In this case the + // remainder and absolute error are also zero. + if (target == 0 || numerator == 0) { + return false; + } + // Otherwise, we want the relative rounding error to be strictly + // less than 0.1%. // The relative error is `remainder / numerator * target`. // We want the relative error less than 1 / 1000: // remainder / numerator * denominator < 1 / 1000 -- cgit From ab5df342e1dc4add20223fab7128f9323a114b8e Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Wed, 22 Aug 2018 12:22:49 -0700 Subject: Add getPartialAmountCeil --- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 35 ++++++++++++++++++++-- 1 file changed, 32 insertions(+), 3 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 758b7ec90..3e70d1b60 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -29,7 +29,7 @@ contract LibMath is /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to calculate partial of. - /// @return Partial value of target. + /// @return Partial value of target rounded down. function getPartialAmount( uint256 numerator, uint256 denominator, @@ -45,8 +45,37 @@ contract LibMath is ); return partialAmount; } - - /// @dev Checks if rounding error >= 0.1%. + + /// @dev Calculates partial value given a numerator and denominator. + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target rounded up. + function getPartialAmountCeil( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (uint256 partialAmount) + { + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + + // SafeDiv rounds down. To use it to round up we need to add + // denominator - 1. This causes anything less than an exact multiple + // of denominator to be rounded up. + partialAmount = safeDiv( + safeAdd(safeMul(numerator, target), safeSub(denominator, 1)), + denominator + ); + return partialAmount; + } + + /// @dev Checks if rounding error > 0.1%. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. -- cgit From 5d70df771b151800b8a04b5569529843701c9fbd Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Wed, 22 Aug 2018 12:22:58 -0700 Subject: Add isRoundingErrorCeil --- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 29 ++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 3e70d1b60..c4aa2abb5 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -107,6 +107,7 @@ contract LibMath is if (target == 0 || numerator == 0) { return false; } + // Otherwise, we want the relative rounding error to be strictly // less than 0.1%. // The relative error is `remainder / numerator * target`. @@ -120,4 +121,32 @@ contract LibMath is isError = safeMul(1000, remainder) >= safeMul(numerator, target); return isError; } + + /// @dev Checks if rounding error > 0.1%. + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to multiply with numerator/denominator. + /// @return Rounding error is present. + function isRoundingErrorCeil( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (bool isError) + { + require(denominator > 0, "DIVISION_BY_ZERO"); + + if (target == 0 || numerator == 0) { + return false; + } + uint256 remainder = mulmod(target, numerator, denominator); + if (remainder == 0) { + return false; + } + remainder = safeSub(denominator, remainder); + isError = safeMul(1000, remainder) >= safeMul(numerator, target); + return isError; + } } -- cgit From 50fab9feb3b80b7d5ac1e94df9af68cad4aaabe0 Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Wed, 22 Aug 2018 12:22:58 -0700 Subject: Improve getPartialAmountCeil docs --- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index c4aa2abb5..d123c55a1 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -65,9 +65,9 @@ contract LibMath is "DIVISION_BY_ZERO" ); - // SafeDiv rounds down. To use it to round up we need to add - // denominator - 1. This causes anything less than an exact multiple - // of denominator to be rounded up. + // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): + // ceil(a / b) = floor((a + b - 1) / b) + // To implement `ceil(a / b)` using safeDiv. partialAmount = safeDiv( safeAdd(safeMul(numerator, target), safeSub(denominator, 1)), denominator -- cgit From 4219af1430f1cfc105d3521616941b7947fde4e3 Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Thu, 23 Aug 2018 14:22:59 -0700 Subject: Add DIVISION_BY_ZERO to getPartialAmount for consistency --- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index d123c55a1..f4e2f1958 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -39,6 +39,8 @@ contract LibMath is pure returns (uint256 partialAmount) { + require(denominator > 0, "DIVISION_BY_ZERO"); + partialAmount = safeDiv( safeMul(numerator, target), denominator @@ -60,10 +62,7 @@ contract LibMath is pure returns (uint256 partialAmount) { - require( - denominator > 0, - "DIVISION_BY_ZERO" - ); + require(denominator > 0, "DIVISION_BY_ZERO"); // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): // ceil(a / b) = floor((a + b - 1) / b) -- cgit From 0fb7617a785b765415cb7f43448c9b8ea905963f Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Thu, 23 Aug 2018 15:18:45 -0700 Subject: Fix incorect modulus --- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index f4e2f1958..1c14dbcae 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -141,10 +141,8 @@ contract LibMath is return false; } uint256 remainder = mulmod(target, numerator, denominator); - if (remainder == 0) { - return false; - } - remainder = safeSub(denominator, remainder); + // TODO: safeMod + remainder = safeSub(denominator, remainder) % denominator; isError = safeMul(1000, remainder) >= safeMul(numerator, target); return isError; } -- cgit From 6734f2f1bcdab8f0d50524a26195707da00bd8ed Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Thu, 23 Aug 2018 15:18:55 -0700 Subject: Add docs --- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 1c14dbcae..8a1444af1 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -74,7 +74,7 @@ contract LibMath is return partialAmount; } - /// @dev Checks if rounding error > 0.1%. + /// @dev Checks if rounding error >= 0.1% when rounding down. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. @@ -121,7 +121,7 @@ contract LibMath is return isError; } - /// @dev Checks if rounding error > 0.1%. + /// @dev Checks if rounding error >= 0.1% when rounding up. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. @@ -137,9 +137,14 @@ contract LibMath is { require(denominator > 0, "DIVISION_BY_ZERO"); + // See the comments in `isRoundingError`. if (target == 0 || numerator == 0) { + // When either is zero, the ideal value and rounded value are zero + // and there is no rounding error. (Although the relative error + // is undefined.) return false; } + // Compute remainder as before uint256 remainder = mulmod(target, numerator, denominator); // TODO: safeMod remainder = safeSub(denominator, remainder) % denominator; -- cgit From f6080367fe3a90762afea76a653c5df1315c45fa Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Fri, 24 Aug 2018 14:11:45 -0700 Subject: Disambiguate the operator precedence --- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 8a1444af1..90ec9e2b6 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -109,9 +109,9 @@ contract LibMath is // Otherwise, we want the relative rounding error to be strictly // less than 0.1%. - // The relative error is `remainder / numerator * target`. + // The relative error is `remainder / (numerator * target)`. // We want the relative error less than 1 / 1000: - // remainder / numerator * denominator < 1 / 1000 + // remainder / (numerator * denominator) < 1 / 1000 // or equivalently: // 1000 * remainder < numerator * target // so we have a rounding error iff: -- cgit From 80291caf7cef16f0b300484755960d92d6750a6a Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Fri, 24 Aug 2018 16:16:44 -0700 Subject: Append -Floor to getPartialAmount and isRoundingError --- .../contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol | 8 ++++---- .../contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol | 4 ++-- .../src/2.0.0/protocol/Exchange/MixinWrapperFunctions.sol | 4 ++-- packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 8 ++++---- 4 files changed, 12 insertions(+), 12 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol b/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol index ab5c6e507..f3a0591b2 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol @@ -320,7 +320,7 @@ contract MixinExchangeCore is // Validate fill order rounding require( - !isRoundingError( + !isRoundingErrorFloor( takerAssetFilledAmount, order.takerAssetAmount, order.makerAssetAmount @@ -376,17 +376,17 @@ contract MixinExchangeCore is { // Compute proportional transfer amounts fillResults.takerAssetFilledAmount = takerAssetFilledAmount; - fillResults.makerAssetFilledAmount = getPartialAmount( + fillResults.makerAssetFilledAmount = getPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.makerAssetAmount ); - fillResults.makerFeePaid = getPartialAmount( + fillResults.makerFeePaid = getPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.makerFee ); - fillResults.takerFeePaid = getPartialAmount( + fillResults.takerFeePaid = getPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.takerFee diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol b/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol index 56b309a1b..20f4b1c33 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol @@ -183,7 +183,7 @@ contract MixinMatchOrders is leftTakerAssetFilledAmount = leftTakerAssetAmountRemaining; // The right order receives an amount proportional to how much was spent. - rightTakerAssetFilledAmount = getPartialAmount( + rightTakerAssetFilledAmount = getPartialAmountFloor( rightOrder.takerAssetAmount, rightOrder.makerAssetAmount, leftTakerAssetFilledAmount @@ -193,7 +193,7 @@ contract MixinMatchOrders is rightTakerAssetFilledAmount = rightTakerAssetAmountRemaining; // The left order receives an amount proportional to how much was spent. - leftTakerAssetFilledAmount = getPartialAmount( + leftTakerAssetFilledAmount = getPartialAmountFloor( rightOrder.makerAssetAmount, rightOrder.takerAssetAmount, rightTakerAssetFilledAmount diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/MixinWrapperFunctions.sol b/packages/contracts/src/2.0.0/protocol/Exchange/MixinWrapperFunctions.sol index 86194f461..1b77cfbcb 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/MixinWrapperFunctions.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/MixinWrapperFunctions.sol @@ -298,7 +298,7 @@ contract MixinWrapperFunctions is // Convert the remaining amount of makerAsset to buy into remaining amount // of takerAsset to sell, assuming entire amount can be sold in the current order - uint256 remainingTakerAssetFillAmount = getPartialAmount( + uint256 remainingTakerAssetFillAmount = getPartialAmountFloor( orders[i].takerAssetAmount, orders[i].makerAssetAmount, remainingMakerAssetFillAmount @@ -350,7 +350,7 @@ contract MixinWrapperFunctions is // Convert the remaining amount of makerAsset to buy into remaining amount // of takerAsset to sell, assuming entire amount can be sold in the current order - uint256 remainingTakerAssetFillAmount = getPartialAmount( + uint256 remainingTakerAssetFillAmount = getPartialAmountFloor( orders[i].takerAssetAmount, orders[i].makerAssetAmount, remainingMakerAssetFillAmount diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 90ec9e2b6..7d58f70ce 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -25,12 +25,12 @@ contract LibMath is SafeMath { - /// @dev Calculates partial value given a numerator and denominator. + /// @dev Calculates partial value given a numerator and denominator rounded down. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to calculate partial of. /// @return Partial value of target rounded down. - function getPartialAmount( + function getPartialAmountFloor( uint256 numerator, uint256 denominator, uint256 target @@ -48,7 +48,7 @@ contract LibMath is return partialAmount; } - /// @dev Calculates partial value given a numerator and denominator. + /// @dev Calculates partial value given a numerator and denominator rounded down. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to calculate partial of. @@ -79,7 +79,7 @@ contract LibMath is /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. /// @return Rounding error is present. - function isRoundingError( + function isRoundingErrorFloor( uint256 numerator, uint256 denominator, uint256 target -- cgit From bc686fcbf3a0f9eea0c96107b9880314027f2d02 Mon Sep 17 00:00:00 2001 From: Remco Bloemen Date: Fri, 24 Aug 2018 16:17:02 -0700 Subject: Stylistic fixes --- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 25 +++++++++++++++++----- 1 file changed, 20 insertions(+), 5 deletions(-) (limited to 'packages/contracts/src/2.0.0/protocol/Exchange') diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 7d58f70ce..0e0fba5d2 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -39,7 +39,10 @@ contract LibMath is pure returns (uint256 partialAmount) { - require(denominator > 0, "DIVISION_BY_ZERO"); + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); partialAmount = safeDiv( safeMul(numerator, target), @@ -62,13 +65,19 @@ contract LibMath is pure returns (uint256 partialAmount) { - require(denominator > 0, "DIVISION_BY_ZERO"); + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): // ceil(a / b) = floor((a + b - 1) / b) // To implement `ceil(a / b)` using safeDiv. partialAmount = safeDiv( - safeAdd(safeMul(numerator, target), safeSub(denominator, 1)), + safeAdd( + safeMul(numerator, target), + safeSub(denominator, 1) + ), denominator ); return partialAmount; @@ -88,7 +97,10 @@ contract LibMath is pure returns (bool isError) { - require(denominator > 0, "DIVISION_BY_ZERO"); + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); // The absolute rounding error is the difference between the rounded // value and the ideal value. The relative rounding error is the @@ -135,7 +147,10 @@ contract LibMath is pure returns (bool isError) { - require(denominator > 0, "DIVISION_BY_ZERO"); + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); // See the comments in `isRoundingError`. if (target == 0 || numerator == 0) { -- cgit