Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Synthesis and capstone
Page 17 of 20

Binary Design Lab

Design, encode, decode, and verify a binary device record.

Lab briefSynthesis and capstone · 7 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Specify a binary record's fields, widths, signedness, byte order, reserved values, and versioning contract.
  • Implement and test encode/decode state transitions, rejecting malformed or ambiguous records.
  • Defend portability with round-trip, boundary, mutation, and compatibility evidence.

Assessment target

Given a binary format and hostile byte stream, derive the parser state, reject invalid lengths/fields, and prove valid round-trip preservation.

Scope boundary

  • Variable-length entropy compression schemes (DEFLATE, protobuf varints) and self-describing serialization (ASN.1, Avro) are omitted to focus on deterministic fixed-width binary record parsing.
  • Cryptographic message authentication (HMAC, signatures) is deferred to Network Security; CRC-16 is evaluated purely as an error-detecting code.
  • Electrical device physics and full RTL syntheses are outside scope.

This lab turns representation theory into an interface that another engineer could implement. Design a 16-byte binary record for a sensor sample and a parser that is safe under malformed input. The record must contain a version, flags, signed temperature, unsigned pressure, timestamp, sequence number, and checksum. You must specify bit widths, byte order, alignment, valid ranges, reserved encodings, checksum coverage, and behavior when the record is truncated or inconsistent.

Specification before encoding

Choose a wire format rather than inheriting the host machine’s struct layout. Host padding, compiler ABI, endianness, and alignment are not stable interchange contracts. Let byte 0 contain an 8-bit version, byte 1 flags, bytes 2–3 a signed 16-bit temperature in hundredths of a degree, bytes 4–7 an unsigned pressure in pascals, bytes 8–11 a 32-bit timestamp, bytes 12–13 a 16-bit sequence, and bytes 14–15 a CRC or checksum. State that all multibyte fields use big-endian order.

The version field supports evolution, but a parser must define whether it accepts unknown versions. Flags need a mask of defined bits; reserved bits should be zero in canonical encodings and rejected or ignored according to policy. Temperature has a signed range [−327.68,327.67][-327.68,327.67] degrees if represented in hundredths. Pressure’s valid physical range may be narrower than the unsigned bit range; validation belongs above bit decoding and should not be conflated with syntax validity.

Pause & Predict: The Packed Struct Portability Trap. Why should systems engineers never parse incoming network or sensor byte streams using a C struct cast like struct Sensor* s = (struct Sensor*)buf; even with #pragma pack(1)? Consider CPU alignment traps, endianness, and aliasing rules before opening the analysis below.

Show hintExpand

Consider what happens when an ARM Cortex-M0 accesses a 32-bit integer at an odd address, or when an x86 host decodes a big-endian network packet.

Reveal analysisExpand

Analysis: Directly overlaying a C struct onto a byte stream introduces three fatal hazards:

  1. Hardware Alignment Traps: On architectures requiring strict natural alignment (such as ARMv6-M Cortex-M0 or older SPARC/MIPS cores), reading a 32-bit field (uint32_t pressure) from an unaligned offset generates an immediate HardFault / Bus Error hardware trap exception.
  2. Endianness Corruption: A multi-byte integer serialized in network big-endian order (0x00018BCD) read on a little-endian host (such as x86-64 or ARM64) is silently interpreted in reverse as 0xCD8B0100 3,448,439,0403{,}448{,}439{,}040 Pa instead of 101,325101{,}325 Pa).
  3. Compiler Undefined Behavior: The C standard prohibits aliasing arbitrary byte buffers through incompatible struct pointers (the strict aliasing rule). Compilers may optimize out subsequent memory re-reads entirely.

Rule: Always deserialize byte streams by explicitly shifting and masking individual octets (val = (buf[0] << 24) | (buf[1] << 16) | ...).

Specify before encode

0 / 4 answered

Why must a binary wire format be formally specified before implementing bit-manipulation and serialization routines?

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Formal wire format specifications prevent C compilers from optimizing bitwise shifts, masks, and byte conversions.
2
Field widths, endianness, and reserved values establish the semantic contract that parser routines must preserve.
3
Bitwise serialization decisions are mathematically independent of the error modes and values observable by consumers.
4
Formal field constraints define unambiguous rejection boundaries for malformed, truncated, or hostile inputs.

Worked encoding

Suppose version is 1, flags are 0b00000101, temperature is -12.34°C, pressure is 101325 Pa, timestamp is 1,700,000,000, and sequence is 42. Temperature scales to -1234. Its 16-bit two’s-complement encoding is 65536−1234=64302=0xFB2E65536-1234=64302=0xFB2E Big-endian bytes are FB 2E. Pressure is 0x00018BCD; timestamp and sequence are encoded similarly. The parser must sign-extend 0xFB2E before dividing by 100; interpreting it as unsigned produces 643.02 and a physically absurd but representable value.

The checksum must cover a defined byte range and have a defined initial value, polynomial or addition rule, reflection policy, and byte order. A simple sum can detect many accidental errors but is weak against rearrangements and deliberate changes. A CRC gives stronger burst-error detection under its specified polynomial, but it is not authentication. If the record crosses an adversarial boundary, add a cryptographic integrity mechanism rather than treating CRC as a security control.

Verify before minimizing

A lab minimizes a four-input control function directly from prose. The resulting circuit is small, but one reserved input combination unexpectedly asserts write-enable.

Evaluate which engineering design artifacts are essential before performing logic minimization on control circuits:

Parser state and failure behavior

A safe parser first checks that at least 16 bytes are available before reading any field. It then decodes into a temporary typed structure, checks version and reserved bits, verifies checksum before trusting payload, validates scaled ranges and sequence policy, and only then publishes the sample. If input may be streamed, use a state machine that accumulates exactly the required header and body bytes; never assume one read returns one record.

The order is a security and correctness boundary. Checking physical range before checking that the bytes belong to a complete record can read beyond the buffer. Publishing temperature before checksum verification can expose attacker-controlled data to control logic. Updating the last-seen sequence before all validation succeeds can permanently reject a later valid record. Use a temporary object and a commit point: prior to commit, parsing is private speculation; after commit, every field satisfies the record invariant.

Failure categories should be distinguishable: truncated input, unsupported version, invalid reserved bits, checksum failure, range violation, and replayed sequence. A caller may choose to drop a corrupt sample but should not treat a checksum failure as a valid zero measurement. Error paths must not leave partially updated shared state.

Worked malformed cases. A 15-byte buffer must be rejected before the parser reads the checksum. A record with version 2 may be rejected or dispatched to a versioned parser, but the default parser must not interpret new fields using old offsets. A valid checksum over a temperature outside the physical sensor range is syntactically valid but semantically invalid. A sequence lower than the last accepted value may be stale, wrapped, or out of order; the protocol must state which.

Implementation and portability

Implement field access with explicit shifts and masks or byte reads, not a packed host struct whose layout is compiler-dependent. Check arithmetic before conversion: a signed input converted to unsigned can become large, and scaling a value can overflow an intermediate type even when the final physical range would fit. Use a wider intermediate and checked multiplication/addition.

The encoder should be the inverse of the decoder on canonical values. Property-based tests can generate valid records, encode and decode them, and assert equality. Negative tests mutate one bit, truncate each possible length, set every reserved bit, and exercise minimum/maximum values. A parser that passes only a hand-written happy-path sample has not established a robust representation contract.

Worked Trace: 16-Byte Sensor Frame Serialization & Decoupled Verification

Let us construct a step-by-step serialization and parser trace for a complete 16-byte sensor telemetry frame:

Input Data Specification:

  • Version = 1 (0x01, 1 byte)
  • Flags = 0b00000101 (0x05, active + calibrated bits, 1 byte)
  • Temperature = −12.34∘C-12.34^\circ\text{C} (signed 16-bit fixed point, 100×100\times scale)
    • Scaled integer: −1234-1234
    • 16-bit two’s complement: 65536−1234=64302=0xFB2E65536 - 1234 = 64302 = \text{0xFB2E}
  • Pressure = 101325 Pa101325\text{ Pa} (unsigned 32-bit integer)
    • Hexadecimal: 0x0001_8BCD (4 bytes).
  • Timestamp = 1,700,000,0001{,}700{,}000{,}000 Unix epoch seconds (unsigned 32-bit integer)
    • Hexadecimal: 0x6554_F100 (4 bytes).
  • Sequence ID = 42 (unsigned 16-bit integer)
    • Hexadecimal: 0x002A (2 bytes).

Step 1: Byte Layout & Big-Endian Octet Placement

Byte [00]: 0x01                  (Version = 1)
Byte [01]: 0x05                  (Flags = 0b00000101)
Byte [02..03]: 0xFB, 0x2E        (Temp: high byte 0xFB, low byte 0x2E)
Byte [04..07]: 0x00, 0x01, 0x8B, 0xCD (Pressure: 0x00018BCD)
Byte [08..11]: 0x65, 0x54, 0xF1, 0x00 (Timestamp: 0x6554F100)
Byte [12..13]: 0x00, 0x2A        (Sequence: 0x002A)

Step 2: Checksum / CRC-16 Calculation (Bytes 0–13) Using CRC-16-CCITT (polynomial x16+x12+x5+1=0x1021x^{16} + x^{12} + x^5 + 1 = \text{0x1021} init 0xFFFF):

  • Processing the 14 payload bytes yields CRC value 0x9D47.
  • Byte [14..15]: 0x9D, 0x47.
  • Full wire frame: 01 05 FB 2E 00 01 8B CD 65 54 F1 00 00 2A 9D 47 (exactly 16 bytes).

Step 3: Invariant Verification during Decoding

  1. Length Check: 16≥1616 \ge 16 bytes present.
  2. Checksum Verification: Compute CRC over bytes 0..13, compare against (buf[14] << 8) | buf[15]. Matches 0x9D47.
  3. Safe Fixed-Point Reconstruction:
    int16_t raw_temp = (int16_t)((buf[2] << 8) | buf[3]); // Preserves signedness: 0xFB2E -> -1234
    double temp_c = (double)raw_temp / 100.0;             // Yields exact -12.34

Counterexample & Failure Mode: The Fixed-Point Unsigned Sign-Extension Disaster

What occurs when a decoder misclassifies the signedness of a fixed-point telemetry stream? Consider an environmental sensor deployed in an Antarctic research station measuring −25.00∘C-25.00^\circ\text{C}

  1. The Correct Wire Pattern:

    • Scaled value: −2500-2500
    • Two’s complement 16-bit encoding: 65536−2500=63036=0xF63C65536 - 2500 = 63036 = \text{0xF63C}
    • Wire bytes: F6 3C.
  2. The Naive Parser Flaw: Suppose the receiving firmware decodes the bytes as an unsigned integer before scaling:

    uint16_t raw = (uint16_t)((buf[2] << 8) | buf[3]); // Evaluates to 63036
    float temp = raw / 100.0f;                         // Computes 63036 / 100.0 = +630.36 C!
  3. Systemic Failure Mode:

    • Instead of −25∘C-25^\circ\text{C} the flight computer or environmental monitor reads +630.36∘C+630.36^\circ\text{C} (hotter than molten lead).
    • Emergency cooling protocols trigger, fire suppressants discharge, or heaters shut off in sub-zero conditions, destroying equipment.
    • Root Cause: The software treated bitfield syntax as an unsigned scalar rather than enforcing the two’s complement arithmetic invariant defined in the interface contract.
Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 5.1.1: Byte-Offset Specification and Alignment Table

Constructionapplication

Produce a byte-offset specification table for a 16-byte telemetry record with explicit field names, widths, signedness, integer scaling factors, valid ranges, and endianness, without relying on compiler-dependent struct padding.

HintExpand

Specify explicit bit/byte widths, signedness, valid numerical ranges, and endianness for every field.

Worked solutionExpand

A complete table names every byte and makes no reliance on host padding. The signed temperature field must explicitly specify two’s complement before scaling; pressure and timestamps must state whether all bit patterns are syntactically valid.

Exercise 5.1.2: Two's-Complement Signed Fixed-Point Encoding

Constructionapplication

Derive the encoded byte sequences for five representative sensor samples, including minimum and maximum representable temperatures and negative scaling boundaries.

HintExpand

Convert negative scaled values using modular complement arithmetic before emitting high-order bytes.

Worked solutionExpand

Encode negative scaled temperature as 216−∣x∣2^{16}-|x| and emit high byte first. Check the result by decoding the emitted bytes and comparing the integer scaled value before converting to floating point.

Exercise 5.1.3: Streaming Parser State Machine and Buffer Framing

Descriptionapplication

Specify a streaming parser state machine with explicit framing states (header, payload, checksum) and deterministic error rejection paths for partial reads.

HintExpand

Define explicit states (header, payload, checksum) and deterministic error rejection paths.

Worked solutionExpand

States should collect header/body bytes, then checksum, then validate and publish. Each read may return fewer bytes than requested. On any error, discard the current record and do not retain partial data as a future header unless the framing protocol says how resynchronization works.

Exercise 5.1.4: CRC Error Detection and Bit-Flip Sensitivity

Verificationapplication

Define a 16-bit CRC polynomial and demonstrate mathematical detection of single-bit corruption and two-byte transpositions over the telemetry frame.

HintExpand

Specify polynomial, initial value, and bit coverage to detect single-bit flips and transpositions.

Worked solutionExpand

A CRC specification must include polynomial, initial value, reflection, final XOR, and coverage. Demonstrate the computed checksum before and after mutation; do not claim security or collision resistance from an unspecified sum.

Exercise 5.1.5: Version-2 Extension and Backward Compatibility

Constructiontransfer

Design a version-2 record extension that enables legacy version-1 parsers to safely reject newer frames while version-2 parsers decode both generations.

HintExpand

Ensure version-1 parsers reject newer versions cleanly while version-2 parsers can decode legacy frames.

Worked solutionExpand

Put new records under version 2 and keep byte offsets unambiguous. A version-1 parser should reject version 2 before interpreting payload, while a version-2 parser can decode a shared prefix and additional fields.

Exercise 5.1.6: Encode-Decode Bijective Round-Trip Invariant Proof

Proofsynthesis

Provide a formal proof sketch showing that decoding an encoded canonical sample D(E(x))D(E(x)) bijectively recovers xx for all valid domain values.

HintExpand

Show field-level injectivity, exact integer scaling preservation, and invertibility of byte reversal.

Worked solutionExpand

Show each field’s encoding is injective over its valid range, byte reversal is undone by decoding, sign extension inverts two’s-complement encoding, and scaling uses an exact integer representation. Canonicality excludes alternate encodings.

Exercise 5.1.7: Hostile Byte Stream Mutation and Fuzzing Matrix

Generalisationtransfer

Construct an adversarial test matrix containing truncated frames, reserved bit corruptions, out-of-range sensor readings, and invalid checksums, stating expected parser outcomes.

HintExpand

Include zero-length frames, partial truncations, reserved-field mutations, and out-of-range sensor values.

Worked solutionExpand

Include length 0, every length 1–15, exact 16, extra trailing bytes, all-zero/all-one values, signed boundaries, each reserved bit, one-bit and burst mutations, stale sequence, and physical limits. Expected outcomes must distinguish reject, accept, and accept-with-warning.

Proof obligations

Let EE be the encoder and DD the decoder. For every canonical sample xx in the declared domain, the primary correctness property is D(E(x))=xD(E(x))=x

This requires more than matching a few examples: each field encoding must be injective, scaling must use an exact integer representation, byte-order reversal must be involutive, and the checksum computed by the decoder must equal the encoder’s checksum over the same bytes.

A second property is rejection soundness: if a byte string fails length, version, reserved-bit, checksum, or range validity, the decoder must not publish a sample. A third is framing progress: after rejecting a record, the streaming parser must either discard exactly the documented frame or resynchronize according to an explicit delimiter rule.

Prove the properties compositionally. First prove field encode/decode lemmas, then prove concatenation preserves offsets, then prove checksum agreement, and finally prove the parser’s commit condition. This mirrors hardware refinement: a large interface becomes manageable when each boundary has a local invariant and the composition preserves it.

Assessment standard

An excellent lab report contains a complete byte-level specification, integer derivations, pseudocode with failure states, generated examples, a test matrix, and proofs tied to stated assumptions. It explains why a packed C struct is insufficient, why CRC is not authentication, why a checksum can be valid for semantically invalid data, and how a future version remains unambiguous. A report that only prints a hexadecimal sample has demonstrated encoding practice but not architectural competence.

An independent engineer or automated test harness should be able to implement the encoder and parser independently from the report and obtain identical bytes for every canonical example.

References & Further Reading

  • IEEE Computer Society. (2019). IEEE Standard for Floating-Point Arithmetic (IEEE Std 754-2019). IEEE.
  • Patterson, D. A., & Hennessy, J. L. (2020). Computer Organization and Design: The Hardware/Software Interface (RISC-V Edition), Chapter 2 & 3. Morgan Kaufmann.
  • Software Engineering Institute, Carnegie Mellon University. (2021). SEI CERT C Coding Standard: Rules for Developing Safe, Reliable, and Secure Systems. Addison-Wesley.