3. Interpreter binárního formátu

Interpreter binárního formátu #

Napište program v jazyce C, který čte binární data ze standardního vstupu a vypisuje je jako text na standardní výstup. Každé číslo je v binárním formátu popsáno jedním descriptorem (1 byte), který určuje typ a formát následujících dat.

Vstup (binární):  [Descriptor][Data][Descriptor][Data]...
                                 ↓                  ↓
Výstup (text):                 3.14                ...

Motivace #

Cílem této úlohy je procvičit si interpretaci jednotlivých bitů a bytů binárních dat. Podobné formáty potkáte u:

  • Binárních spustitelných souborů (více v APO)
  • Kódování obrázků, zvuku a videa
  • Síťových protokolů

Formát Type Descriptoru #

Type Descriptor (8 bitů) #

Bit:  7   6   5   4   3   2   1   0
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │TYP│ ? │ ? │ ? │ ? │ ? │ ? │ ? │
    └───┴───┴───┴───┴───┴───┴───┴───┘
      └── Typ (0=integer, 1=float)

Obecný Type Descriptor pouze určuje, zda se jedná o Integer Type Descriptor nebo Float Type Descriptor. Rozhoduje o tom nejvyšší bit.

  • Typ = 0 Integer Type Descriptor
  • Typ = 1 Float Type Descriptor

Integer Type Descriptor (8 bitů) #

Bit:  7   6   5   4   3   2   1   0
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 0 │SGN│END│S2 │RES│S1 │RES│S0 │
    └───┴───┴───┴───┴───┴───┴───┴───┘
      │   │   │   │       │       │
      │   │   │   └───────┴───────┴── Bity velikosti (S2,S1,S0)
      │   │   └── Endianness (0=little, 1=big)
      │   └── Znaménko (0=unsigned, 1=signed)
      └── Typ (0=integer)
Bit(y) Význam Hodnoty
7 Typ Vždy 0 (integer)
6 Znaménko 0 = unsigned, 1 = signed (two’s complement)
5 Endianness 0 = little-endian, 1 = big-endian
4,2,0 Kód velikosti níže
3,1 - Ignorovat (rezervováno)

Číselnou hodnotu kódu velikosti získáme z těchto tří bitů, kde bit 4 je nejvýznamnější a bit 0 nejméně významný. Matematicky: bit_4 * 4 + bit_2 * 2 + bit_0 * 1.

Velikost čísla v bytes získáme pomocí vzorce, kde Size je hodnota kódu velikosti: pocet_bytes = 2^(Size-1) pro Size > 0. Pro Size = 0 je velikost 0 bytes a tento integer se přeskočí.

Float Type Descriptor (8 bitů) #

Bit:  7   6   5   4   3   2   1   0
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 1 │VEL│REZERVOVÁNO (ignorovat)│
    └───┴───┴───┴───┴───┴───┴───┴───┘
      │   │
      │   └── Velikost (0=float/4B, 1=double/8B)
      └── Typ (1=float)
Bit(y) Význam Hodnoty
7 Typ Vždy 1 (float)
6 Velikost 0 = float (4B), 1 = double (8B)
5-0 - Ignorovat (rezervováno)

⚠️ DŮLEŽITÉ: Hodnoty typu float a double jsou VŽDY big-endian ve formátu IEEE 754, nezávisle na vašem systému!

Formát výstupu #

Každé číslo vypište na samostatný řádek pomocí těchto formátovacích řetězců:

Typ Velikost printf formát Přetypování před výpisem
Unsigned integer 1 byte %u (unsigned)(uint8_t)value
Unsigned integer 2 byty %u (unsigned)(uint16_t)value
Unsigned integer 4 byty %u (unsigned)(uint32_t)value
Unsigned integer 8 bytů %llu (unsigned long long)(uint64_t)value
Signed integer 1 byte %d (int)(int8_t)value
Signed integer 2 byty %d (int)(int16_t)value
Signed integer 4 byty %d (int)(int32_t)value
Signed integer 8 bytů %lld (long long)(int64_t)value
Float 4 byty %.8g -
Double 8 bytů %.17g -
Žádné číslo 0 bytů (ani prázdný řádek) -

DŮLEŽITÉ: Dvojité přetypování je nutné pro správnou interpretaci znaménka!

Chybové stavy #

Program musí skončit s návratovou hodnotou 1 a výpisem "Chyba formátu!\n" na stderr v následujících případech:

  • Hodnota kódu velikosti u integeru je větší než 4 (tj. 5, 6 nebo 7)
  • Vstup je ukončen (EOF) uprostřed čtení dat pro jakékoli číslo

Pomocné funkce pro float/double #

Formát čísel s plovoucí desetinnou čárkou není v jazyce C specifikován, proto musíte použít tyto funkce:

static float float_from_parts(uint8_t sign_bit, uint32_t mantissa_bits, uint32_t exponent_bits) {
    // Add implied top bit
    uint32_t mantissa = (1u << 23) | mantissa_bits;
    int32_t signed_mantissa = sign_bit ? -((int32_t)mantissa) : (int32_t)mantissa;
    int exponent = (int)exponent_bits - 127;
    // -23 is to normalize mantissa from 1xxxx to 1.xxxx
    return ldexpf((float)signed_mantissa, exponent - 23);
}

static double double_from_parts(uint8_t sign_bit, uint64_t mantissa_bits, uint64_t exponent_bits) {
    // Add implied top bit
    uint64_t mantissa = (1ull << 52) | mantissa_bits;
    int64_t signed_mantissa = sign_bit ? -((int64_t)mantissa) : (int64_t)mantissa;
    int exponent = (int)exponent_bits - 1023;
    // -52 is to normalize mantissa from 1xxxx to 1.xxxx
    return ldexp((double)signed_mantissa, exponent - 52);
}

Ukázkový příklad #

Dekódujeme 0x01 0xFF krok po kroku:

  1. Načteme descriptor: 0x01 = 0000 0001

    • Bit 7 = 0 → Je to integer
    • Bit 6 = 0 → unsigned (bez znaménka)
    • Bit 5 = 0 → little-endian
    • Bity 4,2,0 = 001 → Kód velikosti = 1 → 1 byte
  2. Načteme data: 0xFF (1 byte podle kroku 1)

  3. Interpretujeme: unsigned 1-byte hodnota = 255

  4. Výstup: 255\n

Omezení a předpoklady #

  • Maximální velikost integeru: 8 bytů
  • Speciální float/double hodnoty: Pro jednoduchost neuvažujeme NaN, ±∞, denormalizovaná čísla
  • Nula: Hodnoty +0.0 a -0.0 se mohou vyskytnout (obě se vypíší jako 0)

Základní kostra programu #

int main() {
    int descriptor;
    
    while ((descriptor = getchar()) != EOF) {
        if (/* TODO: is integer */) {
            // TODO: extract value based on descriptor

            if (/* TODO: is signed */) {
                switch (size) {
                    case 1:
                        printf("%d\n", (int)(int8_t)value);
                        break;
                    case 2:
                        printf("%d\n", (int)(int16_t)value);
                        break;
                    case 4:
                        printf("%d\n", (int)(int32_t)value);
                        break;
                    case 8:
                        printf("%lld\n", (long long)(int64_t)value);
                        break;
                    default: /* unreachable */
                        break;
                }
            } else {
                switch (size) {
                    case 1:
                        printf("%u\n", (unsigned)(uint8_t)value);
                        break;
                    case 2:
                        printf("%u\n", (unsigned)(uint16_t)value);
                        break;
                    case 4:
                        printf("%u\n", (unsigned)(uint32_t)value);
                        break;
                    case 8:
                        printf("%llu\n", (unsigned long long)(uint64_t)value);
                        break;
                    default:
                        break;
                }
            }
        } else { /* is any floating point number */
            if (/* TODO: is float */) {
                // TODO: extract value based on descriptor

                if (exponent_bits == 0 && mantissa_bits == 0) {
                    // Requirement: both +0.0 and -0.0 must be printed as 0 (no leading -0)
                    // Always print positive zero with the required format.
                    printf("%.8g\n", 0.0f);
                } else {
                    printf("%.8g\n", float_from_parts(sign_bit, mantissa_bits, exponent_bits));
                }
            } else {
                // TODO: extract value based on descriptor

                if (exponent_bits == 0 && mantissa_bits == 0) {
                    // Requirement: both +0.0 and -0.0 must be printed as 0 (no leading -0)
                    printf("%.17g\n", 0.0);
                } else {
                    printf("%.17g\n", double_from_parts(sign_bit, mantissa_bits, exponent_bits));
                }
            }
        }
    }
    
    return 0;
}

Pomocné funkce pro float/double #

Formát čísel s plovoucí desetinnou čárkou není v jazyce C specifikován, proto musíte použít tyto funkce:

#include <stdint.h>
#include <math.h>

/// Reconstruct float from parts of IEEE 754 in a platform independent way
/// that follows the C standard, where float memory layout is not specified.
///
/// Note that this is not very performant.
///
/// @param sign_bit      `0|1`
/// @param mantissa_bits 23 bits of mantissa with top bit implied one (not
///                      considering denormals)
/// @param exponent_bits 8 bits of exponent (with offset signed number format)
static float float_from_parts(uint8_t sign_bit, uint32_t mantissa_bits, uint32_t exponent_bits) {
    // Add implied top bit
    uint32_t mantissa = (1u << 23) | mantissa_bits;
    int32_t signed_mantissa = sign_bit ? -((int32_t)mantissa) : (int32_t)mantissa;
    int exponent = (int)exponent_bits - 127;
    // -23 is to normalize mantissa from 1xxxx to 1.xxxx
    return ldexpf((float)signed_mantissa, exponent - 23);
}

/// Reconstruct double from parts of IEEE 754 in a platform independent way
/// that follows the C standard, where double memory layout is not specified.
///
/// Note that this is not very performant.
///
/// @param sign_bit      `0|1`
/// @param mantissa_bits 52 bits of mantissa with top bit implied one (not
///                      considering denormals)
/// @param exponent_bits 11 bits of exponent (with offset signed number format)
static double double_from_parts(uint8_t sign_bit, uint64_t mantissa_bits, uint64_t exponent_bits)
{
    // Add implied top bit
    uint64_t mantissa = (1ull << 52) | mantissa_bits;
    int64_t signed_mantissa = sign_bit ? -((int64_t)mantissa) : (int64_t)mantissa;
    int exponent = (int)exponent_bits - 1023;
    // -52 is to normalize mantissa from 1xxxx to 1.xxxx
    return ldexp((double)signed_mantissa, exponent - 52);
}

⚠️ POZOR: Před voláním těchto funkcí zkontrolujte speciální případ nuly:

if (exponent_bits == 0 && mantissa_bits == 0) {
    return sign_bit ? -0.0f : 0.0f;  // nebo -0.0 : 0.0 pro double
}

Detailní příklady #

Celková sekvence 01 FF 80 3F 80 00 00 44 34 12 00 je uložena v souboru data.bin.

Pro spuštění Vaše programu, který se bude jmenovat interpreter použijte příkaz:

./interpreter <data.bin

Příklad 1: Unsigned 1-byte integer #

Krok Data Popis
Descriptor 0x01 0000 0001
Interpretace bit 7=0 (integer), bit 6=0 (unsigned), bit 5=0 (LE), bity 4,2,0=001 (1 byte)
Data 0xFF 1 byte
Výsledek 255
Výstup 255

Příklad 2: Signed 2-byte integer (little-endian) #

Krok Data Popis
Descriptor 0x44 0100 0100
Interpretace bit 7=0 (integer), bit 6=1 (signed), bit 5=0 (LE), bity 4,2,0=010 (2 bytes)
Data 0x34 0x12 2 bytes v little-endian
Rekonstrukce Na little-endian systému: `0x34
Výstup 4660

Příklad 3: Float (π) #

Krok Data Popis
Descriptor 0x80 1000 0000
Interpretace bit 7=1 (float), bit 6=0 (4 byty)
Data 0x40 0x49 0x0F 0xDB 4 byty v big-endian
IEEE 754 sign=0, exp=0x80, mantissa=0x490FDB
Výstup 3.1415927

Příklad 4: Kompletní sekvence #

Vstup (hex): 01 FF 80 3F 80 00 00 44 34 12 00

Zpracování:

  1. 0x01 → unsigned 1B → data: 0xFF → výstup: 255
  2. 0x80 → float 4B → data: 0x3F 0x80 0x00 0x00 → výstup: 1
  3. 0x44 → signed 2B LE → data: 0x34 0x12 → výstup: 4660
  4. 0x00 → přeskočit (0 B) → žádná data → žádný výstup

Celkový výstup:

255
1
4660

Testování #

Struktura testů #

Obsah public testů systému Brute je v archivu public_test.

Jeho struktura je následující:

data/public/
├── pub01.txt      # Textová reprezentace vstupu
├── pub01.in       # Vstupní binární data
├── pub01.out      # Očekávaný textový výstup
├── pub02.err      # Očekávaný chybový výstup (pokud není prázdný)
└── ...

Odevzdání #

Povinné zadání
Název v BRUTE 03-interpret
Odevzdávané soubory main.c
Argumenty při spuštění žádné
Návratová hodnota 0 při úspěchu
1 při chybě formátu
Chybový výstup "Chyba formátu!\n" → stderr při chybě
Kompilace clang -pedantic -Wall -std=c99 -O2