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 = 0Integer Type DescriptorTyp = 1Float 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:
-
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
-
Načteme data:
0xFF(1 byte podle kroku 1) -
Interpretujeme: unsigned 1-byte hodnota = 255
-
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í:
0x01→ unsigned 1B → data:0xFF→ výstup:2550x80→ float 4B → data:0x3F 0x80 0x00 0x00→ výstup:10x44→ signed 2B LE → data:0x34 0x12→ výstup:46600x00→ 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ěchu1 při chybě formátu |
| Chybový výstup | "Chyba formátu!\n" → stderr při chybě |
| Kompilace | clang -pedantic -Wall -std=c99 -O2 |