blues / note-c / 22698986002

93%

push

github

Fix COBS code-byte count: ceil(u/254) vs floor(u/254) + 1 (#222)

======================================================================

Background
----------

The Notecard firmware's cobsGuaranteedFit() tells the host library the
maximum number of unencoded binary bytes that will safely fit in the
Notecard's I/O buffer after COBS encoding.  For years, the Notecard used
a simple, slightly conservative formula:

    overhead = 1 + (buflen / 254) + 1
    return buflen - overhead

This estimates the COBS overhead from the *buffer* size rather than from
the (smaller) payload size, which systematically overestimates the number
of code bytes by a small amount.  For the Notecard's 256 KB I/O buffer
(262,144 bytes), this formula reports max = 261,110.

A recent firmware optimization replaced this with a formula intended to
compute the mathematically exact answer.  For the same buffer it now
reports max = 261,114 -- four bytes more than before.

A customer immediately reported that filling the buffer to this new
maximum causes card.binary.get to fail.  The old limit of 261,110 had
always worked; 261,114 does not.

The bug: ceil(u/254) vs floor(u/254) + 1
-----------------------------------------

COBS encoding partitions data into blocks of up to 254 bytes, prefixing
each block with a "code byte" that indicates its length (or the distance
to the next zero).  The central question for buffer-size arithmetic is:
how many code bytes does worst-case encoding produce for u data bytes?

The note-c library computed this as:

    ceil(u / 254)

The correct answer is:

    floor(u / 254) + 1

For most values these are identical.  They diverge at exact multiples
of 254:

    ceil(254 / 254) = 1     WRONG
    floor(254 / 254) + 1 = 2     CORRECT

Why the +1?  Walk through what the encoder actually does with 254
non-zero bytes:

    1. Reserve initial code byte             (code = 1)
    2. Copy 254 data bytes                   (code increments to 0xFF)
    3. code == 0xF... (continued)

1197 of 1373 branches covered (87.18%)

Branch coverage included in aggregate %.

6 of 6 new or added lines in 1 file covered. (100.0%)

2456 of 2540 relevant lines covered (96.69%)

79.85 hits per line