Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Map function - IntegerDivideByZero #8938

Open
FernandoGarcia opened this issue Jun 6, 2023 · 9 comments · May be fixed by #8957
Open

Map function - IntegerDivideByZero #8938

FernandoGarcia opened this issue Jun 6, 2023 · 9 comments · May be fixed by #8957

Comments

@FernandoGarcia
Copy link

Hi!

Someone did a regression in map function and I'm getting this error.

Captura de tela de 2023-06-03 19 03 44

This issue has been fixed here before.

Best regards.

@mcspr
Copy link
Collaborator

mcspr commented Jun 16, 2023

So #7027 is the culprit. But code above does not check the value regardless, so our exception is replaced with a run-time error.

Looking at esp32 where PR was also merged, it was eventually reverted back to original implementation because of errors with larger values. With the provided test (0...180 to 1000...2000 and back), error rate is 0. With 0 and 10000 as min and max - error rate becomes 99%, mapping value and mapping value back are off-by-one :/

Suppose in servo case it makes sense, but not in general func context. Or, calc should take a different value (and btw, divide-by-2 effect is not explained even in servo case besides that it is 'better' :/)

// fixed point math constants to improve accuracy of divide and rounding
constexpr int fixedHalfDecimal = 1;
constexpr int fixedDecimal = fixedHalfDecimal * 2;

func result expected
map(7500, 0, 10000, 10000, 0) 2501 2500
map(2501, 10000, 0, 0, 10000) 7499 7499
map(7499, 0, 10000, 10000, 0) 2502 2501
map(2502, 10000, 0, 0, 10000) 7498 7498
...and so on... ... ...

@TD-er
Copy link
Contributor

TD-er commented Jul 16, 2023

Shouldn't a simple fix like this be enough to prevent these crashes?

if (divisor == 0) return in_min;

Increasing resolution and int overflows with large values are much harder to fix.
But my gut feeling tells me there should be 4 separate cases:

  • dividend > divisor
  • dividend < divisor
  • dividend == divisor
  • dividend == -divisor

This way the first part of the function can be something like this (untested, just notepad memory dump):

long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long divident = out_max - out_min;
  const long divisor = in_max - in_min;
  if (divisor == 0) return in_min;

  const long delta = x - in_min;

  if (divident == divisor) {
    return out_min + delta;
  }
  if (divident == (-1 * divisor)) {
    return out_max + delta;
  }
  ...

@TD-er
Copy link
Contributor

TD-er commented Jul 16, 2023

OK, just thought of something like this (still untested, just some gut feeling programming)

long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long divident = out_max - out_min;
  const long divisor = in_max - in_min;
  if (divisor == 0) return in_min;

  const long delta = x - in_min;

  if (divident == divisor) {
    return out_min + delta;
  }
  if (divident == (-1 * divisor)) {
    return out_max + delta;
  }
  if (abs(divident) > abs(divisor)) {
    const long error = divident % divisor;
    const long factor = (divident + error) / divisor;
    return (delta * factor) + out_min;
  }
  // abs(divident) < abs(divisor)
  const long factor = divisor / divident;
  const long error = out_max - (in_max / factor + out_min);
  return (delta + error) / factor + out_min;
}

Not sure how modulo will act on negative values, so another approach could be something like this:

long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long divident = out_max - out_min;
  const long divisor = in_max - in_min;
  if (divisor == 0) return in_min;

  const long delta = x - in_min;

  if (divident == divisor) {
    return out_min + delta;
  }
  if (divisor < 0 && divident < 0) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (divisor < 0) {
    return map(in_max - x, in_max, in_min, out_min, out_max);
  } else if (divident < 0) {
    return map(in_max - x, in_min, in_max, out_max, out_min);
  }

  if (divident > divisor) {
    const long error = divident % divisor;
    const long factor = (divident + error) / divisor;
    return (delta * factor) + out_min;
  }
  // divident < divisor
  const long factor = divisor / divident;
  const long error = out_max - (in_max / factor + out_min);
  return (delta + error) / factor + out_min;
}

@TD-er
Copy link
Contributor

TD-er commented Jul 16, 2023

Just did a quick test on cpp.sh with the last suggested option:

long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long divident = out_max - out_min;
  const long divisor = in_max - in_min;
  if (divisor == 0) return in_min;

  const long delta = x - in_min;

  if (divident == divisor) {
    return out_min + delta;
  }
  if (divisor < 0 && divident < 0) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (divisor < 0) {
    return map(in_max - x, in_max, in_min, out_min, out_max);
  } else if (divident < 0) {
    return map(in_max - x, in_min, in_max, out_max, out_min);
  }

  if (divident > divisor) {
    const long error = divident % divisor;
    const long factor = (divident + error) / divisor;
    return (delta * factor) + out_min;
  }
  // divident < divisor
  const long factor = divisor / divident;
  const long error = out_max - (in_max / factor + out_min);
  return (delta + error) / factor + out_min;
}

int main()
{
    long value = 0;
    for (size_t i = 1; i < 15; ++i) {
        value = (i/3) * 2500 - 1 + i%3;
        long output = map(value,  0, 10000, 10000, 0);
        long output2 = map(value,  0, 100, 10000, 0);
        long output3 = map(value,  0, 100, 0, 10000);
        std::cout << value << ":\t" << output << "\t" << output2 << "\t" << output3 << "\n";
    }
    
}
0:	10000	10000	0
1:	9999	9900	100
2499:	7501	-239900	249900
2500:	7500	-240000	250000
2501:	7499	-240100	250100
4999:	5001	-489900	499900
5000:	5000	-490000	500000
5001:	4999	-490100	500100
7499:	2501	-739900	749900
7500:	2500	-740000	750000
7501:	2499	-740100	750100
9999:	1	-989900	999900
10000:	0	-990000	1000000
10001:	-1	-990100	1000100

And also mapping to a smaller range:

int main()
{
    long value = 0;
    for (size_t i = 1; i < 15; ++i) {
        value = (i/3) * 2500 - 1 + i%3;
        long output = map(value,  0, 10000, 999, 0);
        long output2 = map(value,  0, 10000, 99, 0);
        long output3 = map(value,  10000, 0, 0, 99);
        std::cout << value << ":\t" << output << "\t" << output2 << "\t" << output3 << "\n";
    }
    
}

Result:

0:	999	99	0
1:	999	99	0
2499:	750	74	-24
2500:	749	74	-24
2501:	749	74	-24
4999:	500	49	-49
5000:	499	49	-49
5001:	499	49	-49
7499:	250	24	-74
7500:	249	24	-74
7501:	249	24	-74
9999:	0	0	-99
10000:	0	0	-99
10001:	0	0	-99

Edit:
Still work to do:

int main()
{
    long value = 0;
    for (size_t i = 1; i < 15; ++i) {
        value = (i/3) * 2500 - 1 + i%3;
        long output = map(value,  0, 10000, 255, 0);
        long output2 = map(value,  0, 10000, 0, 255);
        long output3 = map(value,  10000, 0, 0, 1024);
        long output4 = map(value,  10000, 0, 1024, 0);
        long output5 = map(value,  10000, 0, 0, 10240);
        long output6 = map(value,  10000, 0, 10240, 0);
        std::cout << value << ":\t" << output << "\t" << output2 << "\t" << output3 << "\t" << output4 << "\t" << output5 << "\t" << output6 << "\n";
    }
    
}

Not what it should be...

0:	256	0	-9	-9	0	0
1:	256	0	-9	-9	-1	1
2499:	192	64	-287	268	-2499	2499
2500:	192	64	-287	268	-2500	2500
2501:	192	64	-287	268	-2501	2501
4999:	128	128	-565	545	-4999	4999
5000:	128	128	-565	545	-5000	5000
5001:	128	128	-565	546	-5001	5001
7499:	64	192	-842	823	-7499	7499
7500:	64	192	-843	823	-7500	7500
7501:	64	192	-843	823	-7501	7501
9999:	0	256	-1120	1101	-9999	9999
10000:	0	256	-1120	1101	-10000	10000
10001:	0	256	-1120	1101	-10001	10001

@TD-er
Copy link
Contributor

TD-er commented Jul 17, 2023

Made some progress....

// Example program
# include <iostream>
# include <string>


long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long out_length = out_max - out_min;
  const long in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const long delta = x - in_min;

  if (out_length == in_length) {
    return out_min + delta;
  }

  if (out_length == (-1 * in_length)) {
    return out_max + delta;
  }

  if ((out_length < 0) && (in_length < 0)) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (out_length < 0) {
    return map(in_max - delta, in_min, in_max, out_max, out_min);
  } else if (in_length < 0) {
    return map(in_max - delta, in_max, in_min, out_min, out_max);
  }

  // We now know in_min < in_max and out_min < out_max
  // Make sure x is within range of in_min ... in_max
  if ((x < in_min) || (x > in_max)) {
    long shift_factor = 0;

    if (x < in_min) {
      const long before_min = in_min - x;
      shift_factor = -1 - (before_min / in_length);
    } else if (x > in_max) {
      const long passed_max = x - in_max;
      shift_factor = 1 + (passed_max / in_length);
    }

    if (shift_factor != 0) {
      const long in_shift  = shift_factor * in_length;
      const long out_shift = shift_factor * out_length;
      return map(x, in_min + in_shift, in_max + in_shift, out_min + out_shift, out_max + out_shift);
    }
  }

  const long abs_out_length = abs(out_length);

  if (abs_out_length > abs(in_length)) {
    const long intermediate_divisor = delta == 0 ? 1 : abs_out_length;
    const long intermediate_max     = (0x1FFFFFFF - abs(in_length / 2)) / intermediate_divisor;

    if ((2 * intermediate_max) > abs_out_length) {
      const long intermediate = (delta * intermediate_max * 2 + (in_length / 2)) / in_length - intermediate_max;
      return map(intermediate, -intermediate_max, intermediate_max, out_min, out_max);
    }
  }

  // abs(out_length) < abs(in_length)
  return (delta * out_length + (in_length / 2)) / in_length + out_min;
}

int main()
{
  long value = 0;

  for (size_t i = 1; i < 15; ++i) {
    value = (i / 3) * 2500 - 1 + i % 3;
    const long values[] = {
      map(value, 0,     1000,  255,   0),
      map(value, 0,     1000,  0,     255),
      map(value, 10000, 0,     0,     1024),
      map(value, 10000, 0,     1024,  0),
      map(value, 1000,  0,     0,     10240),
      map(value, 1000,  0,     10240, 0),
      map(value, 0,     1000,  0,     10240),
      map(value, 0,     1000,  10240, 0),
      map(value, 0,     10000, 10240, 0),
      map(value, 10000, 0,     10240, 0)
    };
    std::cout << value << ":";
    constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

    for (size_t i = 0; i < nrvalues; ++i) {
      std::cout << "\t" << values[i];
    }
    std::cout << "\n";
  }
}

With output:

0:	255	0	1024	0	10240	0	0	10240	10240	0
1:	255	0	1024	0	10230	10	10	10230	10239	1
2499:	-382	637	768	256	-15350	25590	25590	-15350	7681	2559
2500:	-382	638	768	256	-15360	25600	25600	-15360	7680	2560
2501:	-383	638	768	256	-15370	25610	25610	-15370	7679	2561
4999:	-1020	1275	512	512	-40950	51190	51190	-40950	5121	5119
5000:	-1020	1275	512	512	-40960	51200	51200	-40960	5120	5120
5001:	-1020	1275	512	512	-40970	51210	51210	-40970	5119	5121
7499:	-1657	1912	256	768	-66550	76790	76790	-66550	2561	7679
7500:	-1657	1913	256	768	-66560	76800	76800	-66560	2560	7680
7501:	-1658	1913	256	768	-66570	76810	76810	-66570	2559	7681
9999:	-2295	2550	0	1024	-92150	102390	102390	-92150	1	10239
10000:	-2295	2550	0	1024	-92160	102400	102400	-92160	0	10240
10001:	-2295	2550	0	1024	-92170	102410	102410	-92170	-1	10241

@mcspr I think this is working very well and stable, without using a single float.

@TD-er
Copy link
Contributor

TD-er commented Jul 17, 2023

And some extra checks for int overflow:

// Example program
# include <iostream>
# include <string>


long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long out_length = out_max - out_min;
  const long in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const long delta = x - in_min;

  if (out_length == in_length) {
    return out_min + delta;
  }

  if (out_length == (-1 * in_length)) {
    return out_max + delta;
  }

  if ((out_length < 0) && (in_length < 0)) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (out_length < 0) {
    return map(in_max - delta, in_min, in_max, out_max, out_min);
  } else if (in_length < 0) {
    return map(in_max - delta, in_max, in_min, out_min, out_max);
  }

  // We now know in_min < in_max and out_min < out_max
  // Make sure x is within range of in_min ... in_max
  if ((x < in_min) || (x > in_max)) {
    long shift_factor = 0;

    if (x < in_min) {
      const long before_min = in_min - x;
      shift_factor = -1 - (before_min / in_length);
    } else if (x > in_max) {
      const long passed_max = x - in_max;
      shift_factor = 1 + (passed_max / in_length);
    }

    if (shift_factor != 0) {
      const long in_shift  = shift_factor * in_length;
      const long out_shift = shift_factor * out_length;
      return map(x, in_min + in_shift, in_max + in_shift, out_min + out_shift, out_max + out_shift);
    }
  }

  const long abs_out_length = abs(out_length);

  if (abs_out_length > abs(in_length)) {
    const long intermediate_max = (0x1FFFFFFF - abs(in_length / 2)) / abs_out_length;

    if (intermediate_max > (abs_out_length >> 2)) {
      const long intermediate = (delta * intermediate_max * 2 + (in_length / 2)) / in_length - intermediate_max;
      return map(intermediate, -intermediate_max, intermediate_max, out_min, out_max);
    }

    // Probably running into integer overflow, so use the slightly less accurate factor approach.
    const long factor = out_length / in_length;
    return (delta * factor) + out_min;
  }

  // abs(out_length) < abs(in_length)

  const unsigned long overflow_estimator =
    (delta > 256 ? (static_cast<unsigned long>(delta) >> 8) : 1) *
    (out_length > 256 ? (static_cast<unsigned long>(out_length) >> 8) : 1) +
    (static_cast<unsigned long>(in_length / 2) >> 8);

  if (overflow_estimator > (1u << 16)) {
    // Would result in integer overflow, so use the slightly less accurate factor approach.
    const long factor = in_length / out_length;

    if (factor != 0) {
      return delta / factor + out_min;
    }
  }
  return (delta * out_length + (in_length / 2)) / in_length + out_min;
}

int main()
{
  long input = 0;

  for (size_t i = 0; i < 15; ++i) {
    input = (i / 3) * 2500 - 1 + i % 3;
    const long values[] = {
      map(input, 0,     1000,  255,      0),
      map(input, 0,     1000,  0,        255),
      map(input, 10000, 0,     100,      10100),
      map(input, 10000, 0,     0,        1024),
      map(input, 10000, 0,     1024,     0),
      map(input, 1000,  0,     0,        10240),
      map(input, 1000,  0,     10240,    0),
      map(input, 0,     1000,  0,        10240),
      map(input, 0,     1000,  10240,    0),
      map(input, 0,     10000, 10240,    0),
      map(input, 10000, 0,     10240,    0),
      map(input, 10000, 0,     10240000, 0),
      map(input, 50,   0,     10240000, 0)
    };
    std::cout << input << ":";
    constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

    for (size_t i = 0; i < nrvalues; ++i) {
      std::cout << "\t" << values[i];
    }
    std::cout << "\n";
  }
}

Result:

-1:	255	0	99	1024	0	10250	-10	-10	10250	10241	-1	-1024	-204800
0:	255	0	100	1024	0	10240	0	0	10240	10240	0	0	0
1:	255	0	101	1024	0	10230	10	10	10230	10239	1	1024	204800
2499:	-382	637	2599	768	256	-15350	25590	25590	-15350	7681	2559	2558976	511795200
2500:	-382	638	2600	768	256	-15360	25600	25600	-15360	7680	2560	2560000	512000000
2501:	-383	638	2601	768	256	-15370	25610	25610	-15370	7679	2561	2561024	512204800
4999:	-1020	1275	5099	512	512	-40950	51190	51190	-40950	5121	5119	5118976	1023795200
5000:	-1020	1275	5100	512	512	-40960	51200	51200	-40960	5120	5120	5120000	1024000000
5001:	-1020	1275	5101	512	512	-40970	51210	51210	-40970	5119	5121	5121024	1024204800
7499:	-1657	1912	7599	256	768	-66550	76790	76790	-66550	2561	7679	7678976	1535795200
7500:	-1657	1913	7600	256	768	-66560	76800	76800	-66560	2560	7680	7680000	1536000000
7501:	-1658	1913	7601	256	768	-66570	76810	76810	-66570	2559	7681	7681024	1536204800
9999:	-2295	2550	10099	0	1024	-92150	102390	102390	-92150	1	10239	10238976	2047795200
10000:	-2295	2550	10100	0	1024	-92160	102400	102400	-92160	0	10240	10240000	2048000000
10001:	-2295	2550	10101	0	1024	-92170	102410	102410	-92170	-1	10241	10241024	2048204800

@TD-er
Copy link
Contributor

TD-er commented Jul 17, 2023

Fixed another issue with "inverted shift" (same range, one counting up, one down) and added a test function to show the "error" compared to the interpolation function using double

// Example program
# include <iostream>
# include <string>


long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long out_length = out_max - out_min;
  const long in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const long delta = x - in_min;

  if (out_length == in_length) {
    return out_min + delta;
  }

  if ((out_length < 0) && (in_length < 0)) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (out_length < 0) {
    return map(in_max - delta, in_min, in_max, out_max, out_min);
  } else if (in_length < 0) {
    return map(in_max - delta, in_max, in_min, out_min, out_max);
  }

  // We now know in_min < in_max and out_min < out_max
  // Make sure x is within range of in_min ... in_max
  if ((x < in_min) || (x > in_max)) {
    long shift_factor = 0;

    if (x < in_min) {
      const long before_min = in_min - x;
      shift_factor = -1 - (before_min / in_length);
    } else if (x > in_max) {
      const long passed_max = x - in_max;
      shift_factor = 1 + (passed_max / in_length);
    }

    if (shift_factor != 0) {
      const long in_shift  = shift_factor * in_length;
      const long out_shift = shift_factor * out_length;
      return map(x, in_min + in_shift, in_max + in_shift, out_min + out_shift, out_max + out_shift);
    }
  }

  const long abs_out_length = abs(out_length);

  if (abs_out_length > abs(in_length)) {
    const long intermediate_max = (0x1FFFFFFF - abs(in_length / 2)) / abs_out_length;

    if (intermediate_max > (abs_out_length >> 2)) {
      const long intermediate = (delta * intermediate_max * 2 + (in_length / 2)) / in_length - intermediate_max;
      return map(intermediate, -intermediate_max, intermediate_max, out_min, out_max);
    }

    // Probably running into integer overflow, so use the slightly less accurate factor approach.
    const long factor = out_length / in_length;
    return (delta * factor) + out_min;
  }

  // abs(out_length) < abs(in_length)

  const unsigned long overflow_estimator =
    (delta > 256 ? (static_cast<unsigned long>(delta) >> 8) : 1) *
    (out_length > 256 ? (static_cast<unsigned long>(out_length) >> 8) : 1) +
    (static_cast<unsigned long>(in_length / 2) >> 8);

  if (overflow_estimator > (1u << 16)) {
    // Would result in integer overflow, so use the slightly less accurate factor approach.
    const long factor = in_length / out_length;

    if (factor != 0) {
      return delta / factor + out_min;
    }
  }
  return (delta * out_length + (in_length / 2)) / in_length + out_min;
}

long test_map(long x, long in_min, long in_max, long out_min, long out_max) {
  const double out_length = out_max - out_min;
  const double in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const double delta = x - in_min;
  const double value =  (delta * out_length + (in_length / 2)) / in_length + out_min;
//  return std::round(value);    
  return value;    
}

long check(long x, long in_min, long in_max, long out_min, long out_max) {
    const long floatvalue = test_map(x, in_min, in_max, out_min, out_max);
    const long map_value = map(x, in_min, in_max, out_min, out_max);
    return floatvalue - map_value;
    
}

int main()
{
  long input = 0;

  for (size_t i = 0; i < 15; ++i) {
    input = (i / 3) * 2500 - 1 + i % 3;
    const long values[] = {
      check(input, 0,     1000,  255,      0),
      check(input, 0,     1000,  0,        255),
      check(input, 10000, 0,     100,      10100),
      check(input, 10000, 0,     10100,    100),
      check(input, 10000, 0,     0,        1024),
      check(input, 10000, 0,     1024,     0),
      check(input, 1000,  0,     0,        10240),
      check(input, 1000,  0,     10240,    0),
      check(input, 0,     1000,  0,        10240),
      check(input, 0,     1000,  10240,    0),
      check(input, 0,     10000, 10240,    0),
      check(input, 10000, 0,     10240,    0),
      check(input, 10000, 0,     10240000, 0),
      check(input, 50,   0,     10240000, 0)
    };
    std::cout << input << ":";
    constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

    for (size_t i = 0; i < nrvalues; ++i) {
      std::cout << "\t" << values[i];
    }
    std::cout << "\n";
  }
}

The "error" for each calculation.

-1:	0	0	0	0	0	0	0	1	1	0	0	1	1	1
0:	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1:	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2499:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
2500:	0	0	0	0	0	0	1	0	0	1	0	0	0	0
2501:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
4999:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
5000:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
5001:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
7499:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
7500:	0	0	0	0	0	0	1	0	0	1	0	0	0	0
7501:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
9999:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
10000:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
10001:	1	0	0	0	0	0	1	0	0	1	1	0	0	0

I think this is as accurate as can be done using only integer calculations :)

@TD-er
Copy link
Contributor

TD-er commented Jul 17, 2023

OK, still could be improved :)

Now even more accurate with large numbers

// Example program
# include <iostream>
# include <string>


long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long out_length = out_max - out_min;
  const long in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const long delta = x - in_min;

  if (out_length == in_length) {
    return out_min + delta;
  }

  if ((out_length < 0) && (in_length < 0)) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (out_length < 0) {
    return map(in_max - delta, in_min, in_max, out_max, out_min);
  } else if (in_length < 0) {
    return map(in_max - delta, in_max, in_min, out_min, out_max);
  }

  // We now know in_min < in_max and out_min < out_max
  // Make sure x is within range of in_min ... in_max
  if ((x < in_min) || (x > in_max)) {
    long shift_factor = 0;

    if (x < in_min) {
      const long before_min = in_min - x;
      shift_factor = -1 - (before_min / in_length);
    } else if (x > in_max) {
      const long passed_max = x - in_max;
      shift_factor = 1 + (passed_max / in_length);
    }

    if (shift_factor != 0) {
      const long in_shift  = shift_factor * in_length;
      const long out_shift = shift_factor * out_length;
      return map(x, in_min + in_shift, in_max + in_shift, out_min + out_shift, out_max + out_shift);
    }
  }

  const long abs_out_length = abs(out_length);

  if (abs_out_length > abs(in_length)) {
    const long intermediate_max = (0x2FFFFFFF - abs(in_length)) / abs_out_length;

    if (intermediate_max > (abs_out_length >> 2)) {
      const long intermediate = (delta * intermediate_max * 2 + (in_length / 2)) / in_length - intermediate_max;
      return map(intermediate, -intermediate_max, intermediate_max, out_min, out_max);
    }

    // Probably running into integer overflow, so use the slightly less accurate factor approach.
    const long factor = out_length / in_length;
    const long error_mod =  out_length % in_length;
    const long error = (delta * error_mod) / in_length;
    return (delta * factor) + out_min + error;
  }

  // abs(out_length) < abs(in_length)
  const unsigned long overflow_estimator =
    (delta > 256 ? (static_cast<unsigned long>(delta) >> 8) : 1) *
    (out_length > 256 ? (static_cast<unsigned long>(out_length) >> 8) : 1) +
    (static_cast<unsigned long>(in_length / 2) >> 8);

  if (overflow_estimator > (1u << 16)) {
    // Would result in integer overflow, so use the slightly less accurate factor approach.
    const long factor = in_length / out_length;
    const long error_mod = in_length % out_length;
    const long error = (error_mod == 0 || delta == 0) ? 0 : out_length / (delta * error_mod);

    return delta / factor + out_min + error;
  }
  return (delta * out_length + (in_length / 2)) / in_length + out_min;
}

long test_map(long x, long in_min, long in_max, long out_min, long out_max) {
  const double out_length = out_max - out_min;
  const double in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const double delta = x - in_min;
  const double value =  (delta * out_length + (in_length / 2)) / in_length + out_min;
//  return std::round(value);    
  return value;    
}

long check(long x, long in_min, long in_max, long out_min, long out_max) {
    const long floatvalue = test_map(x, in_min, in_max, out_min, out_max);
    const long map_value = map(x, in_min, in_max, out_min, out_max);
    return floatvalue - map_value;
    
}

int main()
{
  long input = 0;

  for (size_t i = 0; i < 15; ++i) {
    input = (i / 3) * 2500 - 1 + i % 3;
    const long values[] = {
      check(input, 0,     1000,  255,      0),
      check(input, 0,     1000,  0,        255),
      check(input, 10000, 0,     100,      10100),
      check(input, 10000, 0,     10100,    100),
      check(input, 10000, 0,     0,        1024),
      check(input, 10000, 0,     1024,     0),
      check(input, 1000,  0,     0,        10240),
      check(input, 1000,  0,     10240,    0),
      check(input, 0,     1000,  0,        10240),
      check(input, 0,     1000,  10240,    0),
      check(input, 0,     10000, 10240,    0),
      check(input, 10234567, 0,  1234567,   100),
      check(input, 10000, 0,     10234567, 0),
      check(input, 50,    1,     10234567, 0)
    };
    std::cout << input << ":";
    constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

    for (size_t i = 0; i < nrvalues; ++i) {
      std::cout << "\t" << values[i];
    }
    std::cout << "\n";
  }
}

Output:

-1:	0	0	0	0	0	0	0	1	1	0	0	-44853	2	2
0:	0	0	0	0	0	0	0	0	0	0	0	0	0	1
1:	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2499:	1	0	0	0	0	0	1	0	0	1	0	418	0	0
2500:	0	0	0	0	0	0	1	0	0	1	0	419	1	0
2501:	1	0	0	0	0	0	1	0	0	1	0	419	0	1
4999:	1	0	0	0	0	0	1	0	0	1	0	-21	0	0
5000:	1	0	0	0	0	0	1	0	0	1	0	-22	1	1
5001:	1	0	0	0	0	0	1	0	0	1	0	-22	1	0
7499:	1	0	0	0	0	0	1	0	0	1	0	-32	1	1
7500:	0	0	0	0	0	0	1	0	0	1	0	-32	0	0
7501:	1	0	0	0	0	0	1	0	0	1	0	-32	1	0
9999:	1	0	0	0	0	0	1	0	0	1	0	-43	1	0
10000:	1	0	0	0	0	0	1	0	0	1	0	-44	0	0
10001:	1	0	0	0	0	0	1	0	0	1	1	-44	0	1

@TD-er
Copy link
Contributor

TD-er commented Jul 17, 2023

OK, last update ... (for now) :)

Made it more accurate for large 'delta' and mapping large input range to smaller output range.
Also made it a lot simpler and now with less recursive calls (max 1 recursive call now)

// Example program
# include <iostream>
# include <string>


long map(long x, long in_min, long in_max, long out_min, long out_max) {
  const long out_length = out_max - out_min;
  const long in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  long delta = x - in_min;

  if (out_length == in_length) {
    return out_min + delta;
  }

  if ((out_length < 0) && (in_length < 0)) {
    return map(x, in_max, in_min, out_max, out_min);
  } else if (out_length < 0) {
    return map(in_max - delta, in_min, in_max, out_max, out_min);
  } else if (in_length < 0) {
    return map(in_max - delta, in_max, in_min, out_min, out_max);
  }

  // We now know in_min < in_max and out_min < out_max
  // Make sure x is within range of in_min ... in_max
  if ((x < in_min) || (x > in_max)) {
    long shift_factor = 0;

    if (x < in_min) {
      const long before_min = in_min - x;
      shift_factor = -1 - (before_min / in_length);
    } else if (x > in_max) {
      const long passed_max = x - in_max;
      shift_factor = 1 + (passed_max / in_length);
    }

    if (shift_factor != 0) {
      const long in_shift  = shift_factor * in_length;
      const long out_shift = shift_factor * out_length;
      in_min  += in_shift;
      in_max  += in_shift;
      out_min += out_shift;
      out_max += out_shift;
      delta    = x - in_min;
    }
  }

  if (out_length > in_length) {
    // Map to larger range
    const long factor    = out_length / in_length;
    const long error_mod =  out_length % in_length;
    const long error     = (delta * error_mod) / in_length;
    return (delta * factor) + out_min + error;
  }

  // abs(out_length) < abs(in_length)
  // Map to smaller range
  const long factor = (in_length / out_length);

  const long estimate_full = in_length / factor + out_min;
  const long error         = (delta * (out_max - estimate_full)) / in_length;

  return delta / factor + out_min + error;
}

long test_map(long x, long in_min, long in_max, long out_min, long out_max) {
  const double out_length = out_max - out_min;
  const double in_length  = in_max - in_min;

  if (in_length == 0) { return in_min; }

  if (out_length == 0) { return out_min; }

  const double delta = x - in_min;
  const double value =  (delta * out_length + (in_length / 2)) / in_length + out_min;

  //  return std::round(value);
  return value;
}

long check(long x, long in_min, long in_max, long out_min, long out_max) {
  const long floatvalue = test_map(x, in_min, in_max, out_min, out_max);
  const long map_value  = map(x, in_min, in_max, out_min, out_max);

  return floatvalue - map_value;
}

int main()
{
  long input = 0;

  for (size_t i = 0; i < 15; ++i) {
    input = (i / 3) * 2500 - 1 + i % 3;
    const long values[] = {
      check(input, 0,        1000,   255,      0),
      check(input, 0,        1000,   0,        255),
      check(input, 10000,    0,      100,      10100),
      check(input, 10000,    0,      10100,    100),
      check(input, 10000,    0,      0,        1024),
      check(input, 10000,    0,      1024,     0),
      check(input, 1000,     0,      0,        10240),
      check(input, 1000,     0,      10240,    0),
      check(input, 0,        1000,   0,        10240),
      check(input, 0,        1000,   10240,    0),
      check(input, 0,        10000,  10240,    0),
      check(input, 10234567, -12345, 10234567, 100),
      check(input, 10000,    0,      10234567, 0),
      check(input, 50,       1,      10234567, 0)
    };
    std::cout << input << ":";
    constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

    for (size_t i = 0; i < nrvalues; ++i) {
      std::cout << "\t" << values[i];
    }
    std::cout << "\n";
  }
}

Output:

-1:	0	-1	0	0	0	-1	0	2	2	0	0	-1	2	2
0:	0	0	0	0	0	0	0	0	0	0	0	-1	0	1
1:	-1	0	0	0	-1	0	1	0	0	1	1	-1	0	0
2499:	1	-1	0	0	0	0	1	1	1	1	0	0	0	0
2500:	1	1	0	0	0	0	1	0	0	1	0	0	1	0
2501:	0	0	0	0	0	0	2	0	0	2	1	0	0	1
4999:	1	-1	0	0	0	0	1	1	1	1	0	0	0	0
5000:	1	0	0	0	0	0	1	0	0	1	0	0	1	1
5001:	0	0	0	0	0	0	2	0	0	2	1	0	1	0
7499:	1	-1	0	0	0	0	1	1	1	1	0	0	1	1
7500:	1	1	0	0	0	0	1	0	0	1	0	0	0	0
7501:	0	0	0	0	0	0	2	0	0	2	1	0	1	0
9999:	1	-1	0	0	0	-1	1	1	1	1	0	0	1	0
10000:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
10001:	0	0	0	0	-1	0	2	0	0	2	2	0	0	1

@TD-er TD-er linked a pull request Jul 17, 2023 that will close this issue
TD-er added a commit to TD-er/Arduino that referenced this issue Jul 17, 2023
Fixes: esp8266#8938

Also increase accuracy of mapping and fixing map issues with large values.
Still only using integer operations.

Test function to see absolute error compared to floating point map function using `double` precision floating point values.

```c++
# include <iostream>
# include <string>

long test_map(long x, long in_min, long in_max, long out_min, long out_max) {
    const double out_length = out_max - out_min;
    const double in_length  = in_max - in_min;

    if (in_length == 0) { return in_min; }

    if (out_length == 0) { return out_min; }

    const double delta = x - in_min;
    const double value = (delta * out_length + (in_length / 2)) / in_length + out_min;
//    return std::round(value);
    return value;
}

long check(long x, long in_min, long in_max, long out_min, long out_max) {
    const long floatvalue = test_map(x, in_min, in_max, out_min, out_max);
    const long map_value = map(x, in_min, in_max, out_min, out_max);
    return floatvalue - map_value;
}

int main()
{
    long input = 0;

    for (size_t i = 0; i < 15; ++i) {
        input = (i / 3) * 2500 - 1 + i % 3;
        const long values[] = {
            check(input, 0,        1000,   255,      0),
            check(input, 0,        1000,   0,        255),
            check(input, 10000,    0,      100,      10100),
            check(input, 10000,    0,      10100,    100),
            check(input, 10000,    0,      0,        1024),
            check(input, 10000,    0,      1024,     0),
            check(input, 1000,     0,      0,        10240),
            check(input, 1000,     0,      10240,    0),
            check(input, 0,        1000,   0,        10240),
            check(input, 0,        1000,   10240,    0),
            check(input, 0,        10000,  10240,    0),
            check(input, 10234567, -12345, 10234567, 100),
            check(input, 10000,    0,      10234567, 0),
            check(input, 50,       1,      10234567, 0)
        };
        std::cout << input << ":";
        constexpr size_t nrvalues = sizeof(values) / sizeof(values[0]);

        for (size_t i = 0; i < nrvalues; ++i) {
            std::cout << "\t" << values[i];
        }
        std::cout << "\n";
    }
}
```

Output:
```
-1:	0	-1	0	0	0	-1	0	2	2	0	0	-1	2	2
0:	0	0	0	0	0	0	0	0	0	0	0	-1	0	1
1:	-1	0	0	0	-1	0	1	0	0	1	1	-1	0	0
2499:	1	-1	0	0	0	0	1	1	1	1	0	0	0	0
2500:	1	1	0	0	0	0	1	0	0	1	0	0	1	0
2501:	0	0	0	0	0	0	2	0	0	2	1	0	0	1
4999:	1	-1	0	0	0	0	1	1	1	1	0	0	0	0
5000:	1	0	0	0	0	0	1	0	0	1	0	0	1	1
5001:	0	0	0	0	0	0	2	0	0	2	1	0	1	0
7499:	1	-1	0	0	0	0	1	1	1	1	0	0	1	1
7500:	1	1	0	0	0	0	1	0	0	1	0	0	0	0
7501:	0	0	0	0	0	0	2	0	0	2	1	0	1	0
9999:	1	-1	0	0	0	-1	1	1	1	1	0	0	1	0
10000:	1	0	0	0	0	0	1	0	0	1	0	0	0	0
10001:	0	0	0	0	-1	0	2	0	0	2	2	0	0	1
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants