forked from Imagelibrary/littlefs
d1b254da2c
Initially I thought the fcrc would be sufficient for all of the end-of-commit context, since indicating that there is a new commit is a simple as invalidating the fcrc. But it turns out there are cases that make this impossible. The surprising, and actually common, case, is that of an fcrc that will end up containing a full commit. This is common as soon as the prog_size is big, as small commits are padded to the prog_size at minimum. .------------------. \ | metadata | | | | | | | +-. |------------------| | | | foward CRC ------------. |------------------| / | | | commit CRC -----' | |------------------| | | padding | | | | | |------------------| \ \ | | metadata | | | | | | +-. | | | | | | +-' |------------------| / | | | commit CRC --------' | |------------------| | | | / '------------------' When the commit + crc is all contained in the fcrc, something silly happens with the math behind crcs. Everything in the commit gets canceled out: crc(m) = m(x) x^|P|-1 mod P(x) m ++ crc(m) = m(x) x^|P|-1 + (m(x) x^|P|-1 mod P(x)) crc(m ++ crc(m)) = (m(x) x^|P|-1 + (m(x) x^|P|-1 mod P(x))) x^|P|-1 mod P(x) crc(m ++ crc(m)) = (m(x) x^|P|-1 + m(x) x^|P|-1) x^|P|-1 mod P(x) crc(m ++ crc(m)) = 0 * x^|P|-1 mod P(x) This is the reason the crc of a message + naive crc is zero. Even with an initializer/bit-fiddling, the crc of the whole commit ends up as some constant. So no manipulation of the commit can change the fcrc... But even if this did work, or we changed this scheme to use two different checksums, it would still require calculating the fcrc of the whole commit to know if we need to tweak the first bit to invalidate the unlikely-but-problematic case where we happen to match the fcrc. This would add a large amount of complexity to the commit code. It's much simpler and cheaper to keep the 1-bit counter in the tag, even if it adds another moving part to the system.