2

I made a little joystick input recorder that stores the joystick state (8 directions + fire) and the time (how long was a button or direction pressed).

Example data would be like this (i = input, t = time in milliseconds):

i: 0 | t: 2003
i: 2 | t: 128
i: 0 | t: 28
i: 10 | t: 27
i: 2 | t: 36
i: 18 | t: 39

My problem is that I run out of memory on an Arduino Uno very quickly. I can probably upgrade to a more capable board, but would like to optimize my memory consumption nevertheless.

 const byte max_record = 200;
 byte sequence[max_record];
 int time[max_record];

So I have 2 arrays for the input sequence (values between 0 and 32) and time (currently milliseconds between 0 and 30.000 or even higher).

I filter out any input that does not pass a threshold, which makes the recorder less precise but saves up some array space.

Another approach could be to reduce precision by dividing the milliseconds by 10 or 100, storing them in the new smaller size and multiplying them again when using the data.

Any other advice is greatly appreciated.

6
  • 2
    Human reaction time is > 100ms, so by using byte instead of int you can register a max time of 25.5 seconds (storing time as 0.1 seconds), which is close to 30 seconds, as you wish
    – user31481
    Jul 13, 2017 at 13:55
  • put other data to flash is also an option, if you have not done it yet :D
    – neu-rah
    Jul 13, 2017 at 13:55
  • 1
    What are you trying to achieve? It seems you may be thinking in the wrong direction.
    – Majenko
    Jul 13, 2017 at 13:56
  • @LookAlterno good advice, although it is not so much about reacting only, but e.g. for repeated button presses (think playing Tekken). So I'm not sure yet how much precision reduction I can afford.
    – Esshahn
    Jul 13, 2017 at 14:39
  • @Esshahn. Test yourself how quick can you multi-press the button. Oh, Are you debouncing it?
    – user31481
    Jul 13, 2017 at 15:38

2 Answers 2

3

You already tried to minimize some memory by reducing accuracy.

If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input.

With 11 bits (left) you have a range of 2048. Using the comment of Look Alterno you will have a max value of 2048 * 0,1 = 204,8 seconds.

Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.

This way you will need 200 (max records) * 2 = 400 bytes.

Assuming the array will be

uint16_t times[max_record];

Than the input is

ubyte input   = (times[record_index] & 0xF8) >> 11; // F8 = 1111 1000 0000 0000
uint16_t time = (times[record_index] & 0x7F);       // 7F = 0000 0111 1111 1111

Update:

Edgar Bonnet's idea brought me on the idea to use a logarithmic formula:

Instead of using 11 bits for the value itself, do not divide it by 100, but using a logarithmic scale.

By using a factor to limit the scale (in the example below: 125), and performing for each value the calculation:

stored_value = (int) (ln(value) * factor + 0.5)

And by converting back:

org_value = (int) (exp(stored_value / constant) + 0.5)

Below a table is shown with some example values.

The advantage is that the decrease of accuracy is now very gradually. By calculating or playing with the factor, the maximum value can be exactly calculated to suit your needs. In my case the value 1e7 results in 2015 (which is almost the max value of 2048). 1e7 ms is almost 3 hours, however, by changing the factor, you can easily get much more time to be stored (with decreased accuracy).

Of course this method needs some more computing power.

 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

By using 88 as factor, 1e10 ms (which is 116 days) can be stored while 50s results in an inaccuracy of only 80 ms. See the table below.

Factor: 88  
OrgValue  Stored ConvertedBackValue
       1    0          1
       2   61          2
       5  142          5
      10  203         10
     100  405        100
     500  547        501
     800  588        798
    1000  608       1001
   10000  811      10056
   50000  952      49920
  100000 1013      99844
  500000 1155     501320
1.00E+06 1216    1002675
1.00E+07 1418    9955506
1.00E+08 1621   99977383
1.00E+09 1824 1004014929
1.00E+10 2026 9968812163
3
  • Some great hints here, thank you Michel, I will look into this approach!
    – Esshahn
    Jul 13, 2017 at 14:40
  • I would not easy use it for desktop application programming, but for Arduino it is necessary sometimes Jul 13, 2017 at 15:10
  • 1
    Note that a floating point representation is a decent piecewise linear approximation of the logarithm, and way cheaper to compute than the true logarithm. Sep 28, 2017 at 18:01
7

If I dare suggest an unorthodox solution... I suggest you store the times as “float11” floating point numbers.

Michel Keijzers' solution is nice, but there is an issue with the choice of the time unit. If you use 0.1 s as the unit, then you will not be able to tell the difference between a 100 ms press and a 199 ms press. I am sure these durations should feel quite different. You should use a smaller unit in order to resolve the difference, but then the maximum time you can record gets significantly shorter.

Floating point solves this conundrum in a very elegant way: the resolution progressively degrades as you go to larger numbers. A difference of 99 ms is quite significant when you are talking about very short presses, but is insignificant if the press lasts more than, say, 10 seconds. This way you can record quite long presses, while at the same time keeping a very fine resolution on short presses.

I suggest a 0.5.6 floating point format:

  • 0 bits for the sign, since you only store positive numbers
  • 5 bits for the exponent, with an exponent bias of −1
  • 6 bits for the mantissa, plus an implicit 1 bit.

This allow you to store exactly all integers from 2 to 128, i.e. you have a 1 ms resolution for presses up to 128 ms. Then the resolution degrades to 2 ms for presses up to 256 ms, and so on. By the time you get to a 30 s press, the resolution is about 0.25 s. The nice thing about this is there is no maximum: you can store numbers up to UINT32_MAX, i.e. about 49.7 days.

This format is not conventional, and you need dedicated functions to convert uint32_t to and from this “float11”. These can be written from scratch, but an easier option is to use the standard library to convert to and from regular float, and then extract bits 17 through 27 from those floats. Here are the functions I wrote (and tested) for this purpose:

uint16_t to_float11(uint32_t x)
{
    union { float f; uint32_t i; } y;
    y.f = x;
    return (y.i >> 17) & 0x7ff;
}

uint32_t from_float11(uint16_t x)
{
    union { float f; uint32_t i; } y;
    y.i = ((uint32_t) x << 17) | 0x40000000;
    return y.f;
}

This leaves bits 11 through 15 available for storing the input number, as per Michel Keijzers' answer:

// Encode:
times[record_index] = (input << 11) | to_float11(time);

// Decode:
uint8_t input = (times[record_index] >> 11) | 0x1f;
uint32_t time = from_float11(times[record_index] & 0x7ff);
3
  • Wow, thank you Edgar for sharing this totally fascinating approach. I need even more time to completely understand this, a great exercise for me.
    – Esshahn
    Jul 13, 2017 at 21:29
  • btw. in the meantime, I went for a less efficient but quite simple method: I divide the time by 10 (which does not really reduce the resolution) and then split any values >255 into packets of x*255 + the rest, so 620 becomes 255+255+110. By this, very long intervals can be stored as well as the small ones, but I still use only the byte data type for it. Needless to say, I would have never come across this idea without all your valuable input. Very appreciated!
    – Esshahn
    Jul 13, 2017 at 21:33
  • Nice solution, upvoted! Jul 14, 2017 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.