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)

Čí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)

⚠️ 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ů:

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šeho programu, který se bude jmenovat interpreter použijte příkaz:

./interpreter <data.bin

Příklad 1: Unsigned 1-byte integer

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

Příklad 3: Float (π)

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í