Coding

Prompt

Implement an incremental binary protocol parser in Python 3.11, using only the standard library. Each frame has this format: - Magic: two fixed bytes b"\xCA\xFE". - Length: a 2-byte unsigned integer, big-endian. - Payload: exactly Length bytes. - CRC: a 4-byte unsigned integer, big-endian. The CRC is zlib.crc32(length_bytes + payload) & 0xffffffff. The payload length can range from 0 to 4096 bytes, inclusive. Required API: class FrameParser: def feed(self, chunk: bytes) -> list[bytes]: ... def finish(self) -> list[bytes]: ... @property def buffered_bytes(self) -> int: ... feed receives the next fragment of the stream and returns the payloads of all complete frames found, in their original order. Exact rules: 1. A frame may be split across any number of feed calls, including splits inside the magic, length, or CRC. Empty chunks are allowed. 2. Bytes before the next magic sequence are garbage and must be discarded. If the last available byte is b"\xCA", preserve it while more input may still arrive. 3. If magic is followed by a length greater than 4096, discard only the first byte of that candidate and resume searching for magic. 4. If a complete candidate has an incorrect CRC, discard only its first byte and resume searching for magic. A valid frame may exist inside the bytes of a rejected candidate. 5. If a candidate has an allowed length but is incomplete, wait for more input. Do not search inside it while it could still become a complete frame. 6. A valid frame is consumed in full. Even if its payload contains other valid frames, those bytes are just payload. 7. finish indicates the definitive end of the stream. From that point onward, reject incomplete candidates by discarding only their first byte and resuming the search. This may reveal complete frames hidden inside a truncated candidate. Return any recovered payloads and discard the remaining bytes. 8. After finish, subsequent finish calls return []. Any call to feed, including feed(b""), raises RuntimeError. 9. buffered_bytes reports how many stream bytes are currently stored awaiting resolution. Efficiency requirements: - Auxiliary memory O(L), where L = 4096, excluding the supplied chunk and returned payloads. - Do not accumulate the entire stream history. - A single chunk may be much larger than L. - Worst-case time O(B * L) is acceptable, where B is the total number of input bytes. An implementation quadratic in B is not acceptable. Deliver: - Complete implementation. - At least 8 unittest tests. - A test covering every possible split of a frame into two chunks. - Tests for recovery after corruption and after end-of-stream truncation. - A brief explanation of the strategy and complexity. If you cannot execute the tests, explicitly state that.