Skip to question

Q089FreeFirmware

Parse a bounded Roman board revision

Difficulty
Medium
Topic
Firmware Algorithms
Language
C
Interview prompt

Question

Parse an explicitly sized electrically erasable programmable read-only memory (EEPROM) field as a canonical Roman numeral from I through MMMCMXCIX without allocation or out-of-range reads. The field length is 1..15 bytes. Length 0 or greater than 15 is an invalid argument and is rejected before parsing, even if its bytes would otherwise sum above 3999. Nonnull pointers denote valid live storage for the stated input extent and a separate writable uint16_t output object.

Bounded Roman-revision parser interface with valid, malformed, and overflow outcomes
The parser validates the complete bounded representation before committing its result.
Candidate starting point

Implementation scaffold

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum { ROMAN_OK, ROMAN_EINVAL, ROMAN_ERANGE } roman_rc_t;

static int roman_digit(uint8_t c) {
  switch (c) {
    case 'I': return 1; case 'V': return 5; case 'X': return 10;
    case 'L': return 50; case 'C': return 100; case 'D': return 500;
    case 'M': return 1000; default: return -1;
  }
}

static bool roman_pair(uint8_t a, uint8_t b) {
  return (a == 'I' && (b == 'V' || b == 'X')) ||
         (a == 'X' && (b == 'L' || b == 'C')) ||
         (a == 'C' && (b == 'D' || b == 'M'));
}

static bool roman_is_canonical(const uint8_t *buf, size_t len,
                               uint16_t value) {
  static const uint16_t values[] =
      {1000,900,500,400,100,90,50,40,10,9,5,4,1};
  static const char *const tokens[] =
      {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
  // Implement here: compare the greedy encoding against exactly len bytes.

}

roman_rc_t roman_to_u16(const uint8_t *buf, size_t len, uint16_t *value) {
  // Implement here: validate bounded input, parse pairs, enforce range/canonical form,
  // then write the caller output only on complete success.
}
Reviewed example

Trace one case

Input
bytes="MCMXCIV", length=7
Expected output
success; revision=1994

The subtractive pairs CM, XC, and IV are legal, and re-encoding 1994 reproduces the exact input, proving standard (canonical) spelling.

What to cover

Requirements

  1. Accept only uppercase I, V, X, L, C, D, and M and the six standard subtractive pairs.
  2. Reject null buffer/output pointers and lengths outside 1..15 with ROMAN_EINVAL before reading input. Within that length bound, invalid symbols or subtractive pairs take precedence; after all bytes parse, a total above 3999 returns ROMAN_ERANGE before the canonical-spelling check.
  3. Reject noncanonical spellings by re-encoding the parsed value and comparing every input byte.
  4. Do not call strlen or modify the caller's output until the complete parse succeeds.
Continue practicing
Q022 · Firmware AlgorithmsFind device-tree depth without recursionEasyQ083 · Firmware AlgorithmsAdd decimal lists from a fixed poolMedium