#include <limits>
#include <iostream> // needed for demonstration purpose only
#include <stdexcept> // needed for demonstration purpose only
#include <array> // needed for demonstration purpose only
#include <utility> // needed for demonstration purpose only
namespace safe
{
constexpr static auto max = std::numeric_limits<int>::max();
constexpr static auto min = std::numeric_limits<int>::min();
int negation(int a);
int multiplication(int a, int b);
int division(int a, int b);
int addition(int a, int b);
int subtraction(int a, int b);
}
namespace test
{
template <typename Function>
void unary(Function function, const char* function_name, int a);
template <typename Function>
void binary(Function function, const char* function_name, int a, int b);
}
int main()
{
using namespace safe;
using UnaryFunction = int (*)(int);
using BinaryFunction = int (*)(int, int);
using FunctionName = const char*;
using TestsUnary = std::array<std::pair<UnaryFunction, FunctionName>, 1>;
using TestsBinary = std::array<std::pair<BinaryFunction, FunctionName>, 4>;
TestsUnary unary_functions = {std::make_pair(negation, "negation")};
TestsBinary binary_functions = {std::make_pair(multiplication, "multiplication"),
std::make_pair(division, "division"),
std::make_pair(addition, "addition"),
std::make_pair(subtraction, "subtraction")};
std::array<int, 19> values = { min,
(min / 2) - 1,
min / 2,
(min / 2) + 1,
min / 3,
-4,
-3,
-2,
-1,
0,
1,
2,
3,
4,
max / 3,
(max / 2) - 1,
max / 2,
(max / 2) + 1,
max};
using namespace test;
for ( auto& testable : unary_functions )
{
auto& function = std::get<0>(testable);
auto& name = std::get<1>(testable);
std::cout << name << ":\n";
for ( auto value : values )
{
test::unary(function, name, value);
}
std::cout << '\n';
}
for ( auto& testable : binary_functions )
{
auto& function = std::get<0>(testable);
auto& name = std::get<1>(testable);
std::cout << name << ":\n";
for ( auto value1 : values )
{
for ( auto value2 : values )
{
test::binary(function, name, value1, value2);
}
std::cout << '\n';
}
std::cout << '\n';
}
return 0;
}
namespace safe
{
/**
* Integer multiplication.
*
* Detailed logic:
* if ( a == 0 || b == 0 )
* {
* return 0;
* }
* else if ( a == -1 )
* {
* return negation(b);
* }
* else if ( b == -1 )
* {
* return negation(a);
* }
* else if ( a > 0 && b > 0 )
* {
* const auto limit_result = max; // result will be positive
* const auto limit_a = limit_result / b; // (limit_a + 1) * b > max, which is invalid.
* if ( a > limit_a )
* {
* // error
* }
* }
* else if ( a < 0 && b < 0 )
* {
* const auto limit_result = max; // result will be positive
* const auto limit_a = limit_result / b; // (limit_a - 1) * b > max, which is invalid.
* if ( a < limit_a )
* {
* // error
* }
* }
* else if ( a > 0 && b < 0 )
* {
* const auto limit_result = min; // result will be negative
* const auto limit_a = limit_result / b; // (limit_a + 1) * b < min, which is invalid
* if ( a > limit_a )
* {
* // error
* }
* }
* else if ( a < 0 && b > 0 )
* {
* const auto limit_result = min; // result will be negative
* const auto limit_a = limit_result / b; // (limit_a - 1) * b < min, which is invalid
* if ( a < limit_a )
* {
* // error
* }
* }
* return a * b;
*
*/
int multiplication(int a, int b)
{
if ( (a == 0) || (b == 0) )
{
return 0;
}
if ( a == -1 )
{
return negation(b);
}
if ( b == -1 )
{
return negation(a);
}
const auto limit_result = ((a > 0) == (b > 0)) ? max : min;
const auto limit_a = limit_result / b; // well defined, since b != 0, b != -1.
if ( (0 < a && limit_a < a) || (0 > a && limit_a > a) )
{
throw std::invalid_argument("Multiplication overflow.");
}
return a * b;
}
/**
*
* Integer division can only fail if the divisor is zero.
* It can also fail, it the divisor is -1 (because then only the sign changes and the magnitude isn't guaranteed to fit.)
*/
int division(int a, int b)
{
if ( b == 0 )
{
throw std::invalid_argument("Division by zero.");
}
if ( b == -1 )
{
return negation(a);
}
return a / b; // division is safe, if divisor is not equal to zero.
}
/**
If the operands have different sign, the result cannot be invalid:
w.l.o.g. a < 0 && b > 0
min <= a < 0 < b <= max
Hence,
a >= min && b > 0, therefore a + b >= min + b >= min
b <= max && a < 0, therefore b - (-a) <= max - (-a) <= max
If the operands have the same sign, the result may be invalid.
If a > 0 and b > 0:
If a + b > max, then conversely a > max - b. max - b is valid.
If a < 0 and b < 0:
If a + b < min, then conversely a < min - b, min - b is valid.
*/
int addition(int a, int b)
{
if ( (a > 0 && b > 0 && max - b < a) ||
(a < 0 && b < 0 && a < min - b) )
{
throw std::invalid_argument("Addition overflow.");
}
return a + b;
}
/**
* Technically, this can be done by inverting b and calculating a + (-b).
* This however can fail, if -b cannot be represented.
*
* Hence, the same logic as in addition is applied:
* If a and b have the same sign, the result is valid.
* If a > 0 and b < 0, the result may be too large, however, max + b is a valid number
* If a < 0 and b > 0, the result may be too small, however, min + b is a valid number.
*/
int subtraction(int a, int b)
{
if ( (a > 0 && b < 0 && max + b < a) ||
(a < 0 && b > 0 && a < min + b) )
{
throw std::invalid_argument("Subtraction overflow.");
}
return a - b;
}
/**
-a is invalid, if it cannot be represented in that range.
The integer type either has the range [-2^n, 2^n) or
(-2^n, 2^n)
That is, either the smallest number is -2^n or -2^n + 1,
while the largest number is always 2^n - 1.
Hence, the only value that may not be valid input is the smallest number.
If the range is symmetric, every value can be inverted,
otherwise, the negation fails for the smallest number.
*/
int negation(int a)
{
constexpr static bool symmetric_range = (min + max == 0);
if ( !symmetric_range && a == min )
{
throw std::invalid_argument("The integer representation doesn't allow negation of the smallest integer.");
}
return -a;
}
}
namespace test
{
template <typename Function>
void unary(Function function, const char* function_name, int a)
try
{
function(a);
std::cout << '1';
}
catch ( ... )
{
std::cout << '0';
}
template <typename Function>
void binary(Function function, const char* function_name, int a, int b)
try
{
function(a, b);
std::cout << '1';
}
catch ( ... )
{
std::cout << '0';
}
}
CiNpbmNsdWRlIDxsaW1pdHM+CgojaW5jbHVkZSA8aW9zdHJlYW0+ICAvLyBuZWVkZWQgZm9yIGRlbW9uc3RyYXRpb24gcHVycG9zZSBvbmx5CiNpbmNsdWRlIDxzdGRleGNlcHQ+IC8vIG5lZWRlZCBmb3IgZGVtb25zdHJhdGlvbiBwdXJwb3NlIG9ubHkKI2luY2x1ZGUgPGFycmF5PiAgICAgLy8gbmVlZGVkIGZvciBkZW1vbnN0cmF0aW9uIHB1cnBvc2Ugb25seQojaW5jbHVkZSA8dXRpbGl0eT4gICAvLyBuZWVkZWQgZm9yIGRlbW9uc3RyYXRpb24gcHVycG9zZSBvbmx5CgpuYW1lc3BhY2Ugc2FmZQp7Cgljb25zdGV4cHIgc3RhdGljIGF1dG8gbWF4ID0gc3RkOjpudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKTsKCWNvbnN0ZXhwciBzdGF0aWMgYXV0byBtaW4gPSBzdGQ6Om51bWVyaWNfbGltaXRzPGludD46Om1pbigpOwoKCWludCBuZWdhdGlvbihpbnQgYSk7CgkKCWludCBtdWx0aXBsaWNhdGlvbihpbnQgYSwgaW50IGIpOwoJaW50IGRpdmlzaW9uKGludCBhLCBpbnQgYik7CglpbnQgYWRkaXRpb24oaW50IGEsIGludCBiKTsKCWludCBzdWJ0cmFjdGlvbihpbnQgYSwgaW50IGIpOwp9CgpuYW1lc3BhY2UgdGVzdAp7Cgl0ZW1wbGF0ZSA8dHlwZW5hbWUgRnVuY3Rpb24+Cgl2b2lkIHVuYXJ5KEZ1bmN0aW9uIGZ1bmN0aW9uLCBjb25zdCBjaGFyKiBmdW5jdGlvbl9uYW1lLCBpbnQgYSk7CgkKCXRlbXBsYXRlIDx0eXBlbmFtZSBGdW5jdGlvbj4KCXZvaWQgYmluYXJ5KEZ1bmN0aW9uIGZ1bmN0aW9uLCBjb25zdCBjaGFyKiBmdW5jdGlvbl9uYW1lLCBpbnQgYSwgaW50IGIpOwp9CgppbnQgbWFpbigpCnsKCXVzaW5nIG5hbWVzcGFjZSBzYWZlOwoJdXNpbmcgVW5hcnlGdW5jdGlvbiA9IGludCAoKikoaW50KTsKCXVzaW5nIEJpbmFyeUZ1bmN0aW9uID0gaW50ICgqKShpbnQsIGludCk7Cgl1c2luZyBGdW5jdGlvbk5hbWUgPSBjb25zdCBjaGFyKjsKCXVzaW5nIFRlc3RzVW5hcnkgPSBzdGQ6OmFycmF5PHN0ZDo6cGFpcjxVbmFyeUZ1bmN0aW9uLCBGdW5jdGlvbk5hbWU+LCAxPjsKCXVzaW5nIFRlc3RzQmluYXJ5ID0gc3RkOjphcnJheTxzdGQ6OnBhaXI8QmluYXJ5RnVuY3Rpb24sIEZ1bmN0aW9uTmFtZT4sIDQ+OwoJVGVzdHNVbmFyeSB1bmFyeV9mdW5jdGlvbnMgPSB7c3RkOjptYWtlX3BhaXIobmVnYXRpb24sICJuZWdhdGlvbiIpfTsKCVRlc3RzQmluYXJ5IGJpbmFyeV9mdW5jdGlvbnMgPSB7c3RkOjptYWtlX3BhaXIobXVsdGlwbGljYXRpb24sICJtdWx0aXBsaWNhdGlvbiIpLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdGQ6Om1ha2VfcGFpcihkaXZpc2lvbiwgImRpdmlzaW9uIiksCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0ZDo6bWFrZV9wYWlyKGFkZGl0aW9uLCAiYWRkaXRpb24iKSwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RkOjptYWtlX3BhaXIoc3VidHJhY3Rpb24sICJzdWJ0cmFjdGlvbiIpfTsKCQoJc3RkOjphcnJheTxpbnQsIDE5PiB2YWx1ZXMgPSB7IG1pbiwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChtaW4gLyAyKSAtIDEsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluIC8gMiwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChtaW4gLyAyKSArIDEsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluIC8gMywKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC00LAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLTMsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAtMiwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC0xLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDAsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMSwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAyLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDMsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNCwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXggLyAzLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKG1heCAvIDIpIC0gMSwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXggLyAyLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKG1heCAvIDIpICsgMSwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXh9OwoKCXVzaW5nIG5hbWVzcGFjZSB0ZXN0OwoJZm9yICggYXV0byYgdGVzdGFibGUgOiB1bmFyeV9mdW5jdGlvbnMgKQoJewoJCWF1dG8mIGZ1bmN0aW9uID0gc3RkOjpnZXQ8MD4odGVzdGFibGUpOwoJCWF1dG8mIG5hbWUgPSBzdGQ6OmdldDwxPih0ZXN0YWJsZSk7CgkJc3RkOjpjb3V0IDw8IG5hbWUgPDwgIjpcbiI7CgkJZm9yICggYXV0byB2YWx1ZSA6IHZhbHVlcyApCgkJewoJCQl0ZXN0Ojp1bmFyeShmdW5jdGlvbiwgbmFtZSwgdmFsdWUpOwoJCX0KCQlzdGQ6OmNvdXQgPDwgJ1xuJzsKCX0KCglmb3IgKCBhdXRvJiB0ZXN0YWJsZSA6IGJpbmFyeV9mdW5jdGlvbnMgKQoJewoJCWF1dG8mIGZ1bmN0aW9uID0gc3RkOjpnZXQ8MD4odGVzdGFibGUpOwoJCWF1dG8mIG5hbWUgPSBzdGQ6OmdldDwxPih0ZXN0YWJsZSk7CgkJc3RkOjpjb3V0IDw8IG5hbWUgPDwgIjpcbiI7CgkJZm9yICggYXV0byB2YWx1ZTEgOiB2YWx1ZXMgKQoJCXsKCQkJZm9yICggYXV0byB2YWx1ZTIgOiB2YWx1ZXMgKQoJCQl7CgkJCQl0ZXN0OjpiaW5hcnkoZnVuY3Rpb24sIG5hbWUsIHZhbHVlMSwgdmFsdWUyKTsKCQkJfQoJCQlzdGQ6OmNvdXQgPDwgJ1xuJzsKCQl9CgkJc3RkOjpjb3V0IDw8ICdcbic7Cgl9CglyZXR1cm4gMDsKfQoKbmFtZXNwYWNlIHNhZmUKewoKCgkJLyoqCgkJICogCUludGVnZXIgbXVsdGlwbGljYXRpb24uCgkJICogCQoJCSAqIAlEZXRhaWxlZCBsb2dpYzoKCQkgKiAJaWYgKCBhID09IDAgfHwgYiA9PSAwICkKCQkgKiAJewogCQkqCQlyZXR1cm4gMDsKCQkgKiAJfQoJCSAqICBlbHNlIGlmICggYSA9PSAtMSApCgkJICogIHsKCQkgKiAgICAgIHJldHVybiBuZWdhdGlvbihiKTsKCQkgKiAgfQoJCSAqICBlbHNlIGlmICggYiA9PSAtMSApCgkJICogIHsKCQkgKiAgICAgIHJldHVybiBuZWdhdGlvbihhKTsKCQkgKiAgfQoJCSAqIAllbHNlIGlmICggYSA+IDAgJiYgYiA+IDAgKQoJCSAqIAl7CiAJCSAqCSAJY29uc3QgYXV0byBsaW1pdF9yZXN1bHQgPSBtYXg7IC8vIHJlc3VsdCB3aWxsIGJlIHBvc2l0aXZlCgkJICogCQljb25zdCBhdXRvIGxpbWl0X2EgPSBsaW1pdF9yZXN1bHQgLyBiOyAvLyAobGltaXRfYSArIDEpICogYiA+IG1heCwgd2hpY2ggaXMgaW52YWxpZC4KCQkgKiAJCWlmICggYSA+IGxpbWl0X2EgKQoJCSAqIAkJewogCQkgKgkJCS8vIGVycm9yCgkJICogCQl9CgkJICogCX0KCQkgKiAJZWxzZSBpZiAoIGEgPCAwICYmIGIgPCAwICkKCQkgKiAJewogCQkgKiAJCWNvbnN0IGF1dG8gbGltaXRfcmVzdWx0ID0gbWF4OyAvLyByZXN1bHQgd2lsbCBiZSBwb3NpdGl2ZQoJICAgICAqCSAJY29uc3QgYXV0byBsaW1pdF9hID0gbGltaXRfcmVzdWx0IC8gYjsgLy8gKGxpbWl0X2EgLSAxKSAqIGIgPiBtYXgsIHdoaWNoIGlzIGludmFsaWQuCgkJICogCQlpZiAoIGEgPCBsaW1pdF9hICkKCQkgKiAJCXsKCQkgKgkJCS8vIGVycm9yCgkJICogCQl9CgkJICogCX0KCQkgKiAJZWxzZSBpZiAoIGEgPiAwICYmIGIgPCAwICkKCQkgKiAJewogCQkgKiAJCWNvbnN0IGF1dG8gbGltaXRfcmVzdWx0ID0gbWluOyAvLyByZXN1bHQgd2lsbCBiZSBuZWdhdGl2ZQoJCSAqIAkJY29uc3QgYXV0byBsaW1pdF9hID0gbGltaXRfcmVzdWx0IC8gYjsgLy8gKGxpbWl0X2EgKyAxKSAqIGIgPCBtaW4sIHdoaWNoIGlzIGludmFsaWQKCQkgKiAJCWlmICggYSA+IGxpbWl0X2EgKQoJCSAqIAkJewogIAkJICogCQkJLy8gZXJyb3IKCQkgKiAJCX0KCQkgKiAJfQoJCSAqIAllbHNlIGlmICggYSA8IDAgJiYgYiA+IDAgKQoJCSAqCXsKCQkgKgkJY29uc3QgYXV0byBsaW1pdF9yZXN1bHQgPSBtaW47IC8vIHJlc3VsdCB3aWxsIGJlIG5lZ2F0aXZlCgkJICoJCWNvbnN0IGF1dG8gbGltaXRfYSA9IGxpbWl0X3Jlc3VsdCAvIGI7IC8vIChsaW1pdF9hIC0gMSkgKiBiIDwgbWluLCB3aGljaCBpcyBpbnZhbGlkCgkJICoJCWlmICggYSA8IGxpbWl0X2EgKQoJCSAqCQl7CgkJICoJCQkvLyBlcnJvcgoJCSAqCQl9CgkJICogCX0KCQkgKglyZXR1cm4gYSAqIGI7CgkJICogCgkJICovCglpbnQgbXVsdGlwbGljYXRpb24oaW50IGEsIGludCBiKQoJewoJCWlmICggKGEgPT0gMCkgfHwgKGIgPT0gMCkgKQoJCXsKCQkJcmV0dXJuIDA7CgkJfQoJCWlmICggYSA9PSAtMSApCgkJewoJCQlyZXR1cm4gbmVnYXRpb24oYik7CgkJfQoJCWlmICggYiA9PSAtMSApCgkJewoJCQlyZXR1cm4gbmVnYXRpb24oYSk7CgkJfQoJCWNvbnN0IGF1dG8gbGltaXRfcmVzdWx0ID0gKChhID4gMCkgPT0gKGIgPiAwKSkgPyBtYXggOiBtaW47CgkJY29uc3QgYXV0byBsaW1pdF9hID0gbGltaXRfcmVzdWx0IC8gYjsgLy8gd2VsbCBkZWZpbmVkLCBzaW5jZSBiICE9IDAsIGIgIT0gLTEuCgkJaWYgKCAoMCA8IGEgJiYgbGltaXRfYSA8IGEpIHx8ICgwID4gYSAmJiBsaW1pdF9hID4gYSkgKQoJCXsKCQkJdGhyb3cgc3RkOjppbnZhbGlkX2FyZ3VtZW50KCJNdWx0aXBsaWNhdGlvbiBvdmVyZmxvdy4iKTsKCQl9CgkJcmV0dXJuIGEgKiBiOwoJfQoKCS8qKgoJICogCgkgKiAJSW50ZWdlciBkaXZpc2lvbiBjYW4gb25seSBmYWlsIGlmIHRoZSBkaXZpc29yIGlzIHplcm8uCgkgKiAgSXQgY2FuIGFsc28gZmFpbCwgaXQgdGhlIGRpdmlzb3IgaXMgLTEgKGJlY2F1c2UgdGhlbiBvbmx5IHRoZSBzaWduIGNoYW5nZXMgYW5kIHRoZSBtYWduaXR1ZGUgaXNuJ3QgZ3VhcmFudGVlZCB0byBmaXQuKQoJICovCglpbnQgZGl2aXNpb24oaW50IGEsIGludCBiKQoJewoJCWlmICggYiA9PSAwICkKCQl7CgkJCXRocm93IHN0ZDo6aW52YWxpZF9hcmd1bWVudCgiRGl2aXNpb24gYnkgemVyby4iKTsKCQl9CgkJaWYgKCBiID09IC0xICkKCQl7CgkJCXJldHVybiBuZWdhdGlvbihhKTsKCQl9CgkJcmV0dXJuIGEgLyBiOyAvLyBkaXZpc2lvbiBpcyBzYWZlLCBpZiBkaXZpc29yIGlzIG5vdCBlcXVhbCB0byB6ZXJvLgoJfQoKCS8qKgoJCUlmIHRoZSBvcGVyYW5kcyBoYXZlIGRpZmZlcmVudCBzaWduLCB0aGUgcmVzdWx0IGNhbm5vdCBiZSBpbnZhbGlkOgoJCSAgIHcubC5vLmcuIGEgPCAwICYmIGIgPiAwCgkJCW1pbiA8PSBhIDwgMCA8IGIgPD0gbWF4CgkJCUhlbmNlLCAKCQkJYSA+PSBtaW4gJiYgYiA+IDAsIHRoZXJlZm9yZSBhICsgYiAgICA+PSBtaW4gKyBiICAgID49IG1pbgoJCQliIDw9IG1heCAmJiBhIDwgMCwgdGhlcmVmb3JlIGIgLSAoLWEpIDw9IG1heCAtICgtYSkgPD0gbWF4CgkJSWYgdGhlIG9wZXJhbmRzIGhhdmUgdGhlIHNhbWUgc2lnbiwgdGhlIHJlc3VsdCBtYXkgYmUgaW52YWxpZC4KCQkgIElmIGEgPiAwIGFuZCBiID4gMDoKCQkgICAgSWYgYSArIGIgPiBtYXgsIHRoZW4gY29udmVyc2VseSBhID4gbWF4IC0gYi4gbWF4IC0gYiBpcyB2YWxpZC4KCQkgIElmIGEgPCAwIGFuZCBiIDwgMDoKCQkgIAlJZiBhICsgYiA8IG1pbiwgdGhlbiBjb252ZXJzZWx5IGEgPCBtaW4gLSBiLCBtaW4gLSBiIGlzIHZhbGlkLgoJICovCglpbnQgYWRkaXRpb24oaW50IGEsIGludCBiKQoJewoJCWlmICggKGEgPiAwICYmIGIgPiAwICYmIG1heCAtIGIgPCBhKSB8fAoJCSAgICAgKGEgPCAwICYmIGIgPCAwICYmIGEgPCBtaW4gLSBiKSApCgkJewoJCQl0aHJvdyBzdGQ6OmludmFsaWRfYXJndW1lbnQoIkFkZGl0aW9uIG92ZXJmbG93LiIpOwoJCX0KCQlyZXR1cm4gYSArIGI7Cgl9CgoJLyoqCgkgKiBUZWNobmljYWxseSwgdGhpcyBjYW4gYmUgZG9uZSBieSBpbnZlcnRpbmcgYiBhbmQgY2FsY3VsYXRpbmcgYSArICgtYikuCgkgKiBUaGlzIGhvd2V2ZXIgY2FuIGZhaWwsIGlmIC1iIGNhbm5vdCBiZSByZXByZXNlbnRlZC4KCSAqIAoJICogSGVuY2UsIHRoZSBzYW1lIGxvZ2ljIGFzIGluIGFkZGl0aW9uIGlzIGFwcGxpZWQ6CgkgKiBJZiBhIGFuZCBiIGhhdmUgdGhlIHNhbWUgc2lnbiwgdGhlIHJlc3VsdCBpcyB2YWxpZC4KCSAqIElmIGEgPiAwIGFuZCBiIDwgMCwgdGhlIHJlc3VsdCBtYXkgYmUgdG9vIGxhcmdlLCBob3dldmVyLCBtYXggKyBiIGlzIGEgdmFsaWQgbnVtYmVyCgkgKiBJZiBhIDwgMCBhbmQgYiA+IDAsIHRoZSByZXN1bHQgbWF5IGJlIHRvbyBzbWFsbCwgaG93ZXZlciwgbWluICsgYiBpcyBhIHZhbGlkIG51bWJlci4KCSAqLwoJaW50IHN1YnRyYWN0aW9uKGludCBhLCBpbnQgYikKCXsKCQlpZiAoIChhID4gMCAmJiBiIDwgMCAmJiBtYXggKyBiIDwgYSkgfHwKCQkgICAgIChhIDwgMCAmJiBiID4gMCAmJiBhIDwgbWluICsgYikgKQoJCXsKCQkJdGhyb3cgc3RkOjppbnZhbGlkX2FyZ3VtZW50KCJTdWJ0cmFjdGlvbiBvdmVyZmxvdy4iKTsKCQl9CgkJcmV0dXJuIGEgLSBiOwoJfQoKCS8qKgoJCS1hIGlzIGludmFsaWQsIGlmIGl0IGNhbm5vdCBiZSByZXByZXNlbnRlZCBpbiB0aGF0IHJhbmdlLgoJCVRoZSBpbnRlZ2VyIHR5cGUgZWl0aGVyIGhhcyB0aGUgcmFuZ2UgWy0yXm4sIDJebikgb3IKCQkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICgtMl5uLCAyXm4pCgkJVGhhdCBpcywgZWl0aGVyIHRoZSBzbWFsbGVzdCBudW1iZXIgaXMgLTJebiBvciAtMl5uICsgMSwKCQkgd2hpbGUgdGhlIGxhcmdlc3QgbnVtYmVyIGlzIGFsd2F5cyAyXm4gLSAxLgoJCQoJCUhlbmNlLCB0aGUgb25seSB2YWx1ZSB0aGF0IG1heSBub3QgYmUgdmFsaWQgaW5wdXQgaXMgdGhlIHNtYWxsZXN0IG51bWJlci4KCQkKCQlJZiB0aGUgcmFuZ2UgaXMgc3ltbWV0cmljLCBldmVyeSB2YWx1ZSBjYW4gYmUgaW52ZXJ0ZWQsCgkJb3RoZXJ3aXNlLCB0aGUgbmVnYXRpb24gZmFpbHMgZm9yIHRoZSBzbWFsbGVzdCBudW1iZXIuCgkqLwoJaW50IG5lZ2F0aW9uKGludCBhKQoJewoJCWNvbnN0ZXhwciBzdGF0aWMgYm9vbCBzeW1tZXRyaWNfcmFuZ2UgPSAobWluICsgbWF4ID09IDApOwoJCWlmICggIXN5bW1ldHJpY19yYW5nZSAmJiBhID09IG1pbiApCgkJewoJCQl0aHJvdyBzdGQ6OmludmFsaWRfYXJndW1lbnQoIlRoZSBpbnRlZ2VyIHJlcHJlc2VudGF0aW9uIGRvZXNuJ3QgYWxsb3cgbmVnYXRpb24gb2YgdGhlIHNtYWxsZXN0IGludGVnZXIuIik7CgkJfQoJCXJldHVybiAtYTsKCX0KfQoKbmFtZXNwYWNlIHRlc3QKewoJdGVtcGxhdGUgPHR5cGVuYW1lIEZ1bmN0aW9uPgoJdm9pZCB1bmFyeShGdW5jdGlvbiBmdW5jdGlvbiwgY29uc3QgY2hhciogZnVuY3Rpb25fbmFtZSwgaW50IGEpCgl0cnkKCXsKCQlmdW5jdGlvbihhKTsKCQlzdGQ6OmNvdXQgPDwgJzEnOwoJfQoJY2F0Y2ggKCAuLi4gKQoJewoJCXN0ZDo6Y291dCA8PCAnMCc7Cgl9CgkKCXRlbXBsYXRlIDx0eXBlbmFtZSBGdW5jdGlvbj4KCXZvaWQgYmluYXJ5KEZ1bmN0aW9uIGZ1bmN0aW9uLCBjb25zdCBjaGFyKiBmdW5jdGlvbl9uYW1lLCBpbnQgYSwgaW50IGIpCgl0cnkKCXsKCQlmdW5jdGlvbihhLCBiKTsKCQlzdGQ6OmNvdXQgPDwgJzEnOwoJfQoJY2F0Y2ggKCAuLi4gKQoJewoJCXN0ZDo6Y291dCA8PCAnMCc7Cgl9Cn0K