Use one byte for width not two

[drtonyr]

Hello, I come here from https://github.com/daniel-thompson/wasp-os and thank you for your font code.

We are always short of space with micropython. I was digging into the code and found these lines:

ifb = lambda l : l[0] | (l[1] << 8)
...
    width = ifb(_mvfont[doff : ])

That is, within _font there are two bytes allocated to the width of each character. This seems excessive to me, most characters have a width that fits easily into one byte and there are only two bytes allocated to the data offset, so a font that has characters wider than 256 probably isn't going to fit into the format anyway. max_width is already calculated, so it would be a question of eliminating the high width byte in _font and outputing something like:

def get_ch(ch):
    oc = ord(ch)
    ioff = 2 * (oc - 32 + 1) if oc >= 32 and oc <= 126 else 0
    doff = ifb(_mvi[ioff : ])
    width = i_mvfont[doff] #  don't call ifb as only reading one byte

    next_offs = doff + 1 + ((width - 1)//8 + 1) * 24  # + 1 not + 2
    return _mvfont[doff + 1:next_offs], 24, width  # + 1 not + 2

[peterhinch]

The principal aim of creating Python font files is to enable them to be frozen as bytecode. This means that the font consumes only Flash space. RAM usage is minimal, and would not be reduced significantly by this change. Further, there have been rare use case where users have wanted very large fonts e.g. for digital clock displays.

[drtonyr]

Yes, and flash space can be at a premium. As stated above, I come from I come here from https://github.com/daniel-thompson/wasp-os and we need space.

The font access code is autogenerated. At the time of generation you know whether you need one byte or two for the width. Using one byte when you need one byte and two bytes when you need two bytes gives you the best of both worlds. In the vast majority of cases you end up with simpler code and reduced memory space. In the odd case that you have fonts that are more than 256 wide then nothing changes.

I hope this gives sufficient background to the issue.

[peterhinch]

I take your points - it would be a nice optimisation. I'll have to consider priorities re finding time to do it.

[drtonyr]

Thank you @peterhinch. Last night I thought of some much bigger memory optimisations which I'll work on and let you know the progress.

As I've taken your time to read this, I have (what I hope is) a very quick question. In font_to_py.py you say:

# PYTHON FILE WRITING                                                           
# The index only holds the start of data so can't read next_offset but must     
# calculate it.  

and you make use of the variable next_offs. This suggests that at some time in the past the code made two lookups in the index table, one to get the start of the _font data and one to get the end. This no longer seems to happen anywhere (perhaps this was necessary in order to implement sparse fonts). So, can I assume that the comment above will remain true, that is you'll always calculate the data length? If I can assume this then we could potentially reorder all the data in _font, there is no need for the values in _index to be in order.

Or, phrasing this more tersely, if I reordered _index and _font to match, would you be upset?

[peterhinch]

I don't follow your point about next_offs: it is used to calculate the exact size of the memoryview slice. Obviously the variable could be eliminated by combining these two lines into one, but I chose readability:

    next_offs = doff + 2 + ((width - 1)//8 + 1) * {0}
    return _mvfont[doff + 2:next_offs], {0}, width

As a general point I put a lot of effort into reducing the RAM usage but did not optimise Flash size. You are the first user in six years to express concern over Flash size so I need to think hard about any major changes here.

[drtonyr]

Thanks, I'm trying to scope out the extent of changes that you'll accept.

_index has ordered values, but the ordering isn't currently used. Would you accept a MR where _index didn't have ordered values? The data in _font would be reordered in the same way as _index so all the current runtime code would keep working.

[peterhinch]

the ordering isn't currently used

It is ordered to enable the binary search.

You seem to be envisaging fairly radical changes. You started out with a clear message about character width, but since then I've become increasingly unclear about the big picture behind your thinking. I'm puzzled by your comments about next_offs and now this observation about ordering. I can't see where this discussion is heading.

Maybe the best way would be for you to implement these changes and submit a PR. I should warn you there are a lot of special cases that need to be tested.

[peterhinch]

Now that I've had time to consider this, I think you are wrong about changing the field width: the data is not stored as you suggest. The output data is a bitmap whose dimensions are the actual size of the current glyph. Consider again this code:

    next_offs = doff + 2 + ((width - 1)//8 + 1) * {0}
    return _mvfont[doff + 2:next_offs], {0}, width

The height value has an integer substituted in the emitted code, so for a typical font with height==17 you would see

    next_offs = doff + 2 + ((width - 1)//8 + 1) * 17
    return _mvfont[doff + 2:next_offs], 17, width

The only overhead here is that if the width of a glyph is N bits, its width in bytes is rounded up to the minimum required to hold N bits. While this overhead could be eliminated, the gain would be small and would be offset by a substantial increase in code size.

I will need a convincing case to be made to consider making changes to this code.

[drtonyr]

the ordering isn't currently used

It is ordered to enable the binary search.

Not that I've found. I've seen a binary search on _mvsp, but I haven't seen a binary search on _index.

Now that I've had time to consider this, I think you are wrong about changing the field width: the data is not stored as you suggest.

I'm really not following you here. I started by saying:

ifb = lambda l : l[0] | (l[1] << 8)
...
    width = ifb(_mvfont[doff : ])

That is, within _font there are two bytes allocated to the width of each character.

If max_width is 255 or less then we could replace width = ifb(_mvfont[doff : ]) with width = _mvfont[doff] and save a byte per character. If max_width is 256 or more we should continue to output the current code.

Anyway, I can see far more opportunity to save space than one byte per character. I'm going to close this issue now so that things don't get any more confused. Thanks a lot for your help.

[peterhinch]

I created a test font based on FreeSans.ttf at a target height of 12 pixels with the default character set of 95 glyphs. The file size was 7512 bytes. The saving from using one byte instead of two would be 95 bytes or 1.26%. My view is that this is not worth the added complexity, given that I also have to cope with sizes > 256 pixels.

The binary search is here. It is only emitted for sparse glyph sets.

As I'm sure you've gathered, I'm not keen on these changes - the code is already rather complex owing to the number of special cases catered for, and for 99% of users Flash space is not an issue. I suggest you maintain your own fork.