Информатика · урок за напреднали

От байтове
до мелница

Как непознат файл се превръща в 3D модел на екрана и какво научаваме по пътя за това как компютрите пазят данни.

53
37
4D
46
01
00
00
00
AC
12
00
00
Защо тази задача

Един пълен цикъл

Повечето програми започват от готови данни. Тук започваме от нулата: от суровите байтове.

🧱

Байтове

шестнайсетичен редактор, без документация

→
🔍

Структура

заглавна част, блокове, типове

→
⚙️

Алгоритъм

C# програма, която чете и превръща

→
📦

Данни

масиви, записани в JSON

→
🏠

Картина

Three.js показва модела

Всяка стъпка е отделна професия: анализ, проектиране, програмиране, работа с данни, графика.

Основата

Във файла няма числа. Има байтове.

Всеки файл е редица от байтове: числа от 0 до 255. Едни и същи четири байта:

00
00
80
3F
Чети ги като…Получаваш
цяло число без знак (uint)1 065 353 216
реално число (float)1.0
четири отделни байта (byte)0, 0, 128, 63

Байтовете сами не означават нищо. Смисъл им дава типът, тоест договорката как да ги четем.

Защо в C# има толкова типове

Колко байта и как да ги разбираме

ТипБайтаОбхватВ 3D модела
byte10 … 255цвят, нормала
ushort / short20 … 65 535 / ±32 767индекси на триъгълници
uint / int40 … 4,29 млрд. / ±2,1 млрд.брой върхове, размери
Half2~3 цифри точностпозиции на върховете
float4~7 цифри точностграниците на модела
double8~15 цифри точностне се ползва

Изборът е компромис: повече байтове означава по-голям обхват и точност, но повече памет. Играта избира Half за позициите и пести половината място.

Откритието на Белослава

ÿÿÿÿ на всеки 24 байта

FFÿ
FFÿ
FFÿ
FFÿ

Като число

Като uint = 4 294 967 295

Като int = −1

Знакът е в най-горния бит. 32 единици без знак са най-голямото число, а със знак са −1 (допълнителен код).

А всъщност

Цветът на върха: червено, зелено, синьо, прозрачност = 255, 255, 255, 255, бяло и непрозрачно.

Повтаря се на всеки 24 байта, защото един връх заема точно 24 байта. Това е stride.

Ред на байтовете

Little-endian и big-endian

Как се записва числото, когато заема повече от един байт? Отзад напред или отпред назад?

Little-endian · младшият байт първи

53
37
4D
46

= 0x464D3753 = 1 179 465 555

Intel, AMD, ARM: почти всички компютри и телефони днес. Нашият S7M файл.

Big-endian · старшият байт първи

53
37
4D
46

= 0x53374D46 = 1 396 133 190

Мрежовите протоколи и форматите PNG и JPEG.

Редът се определя от формата на файла, не от операционната система. Затова файлът се чете еднакво на Windows, macOS и Linux: всяка програма следва договорката на формата.

Пробвай сам · докосни и пиши

Четири байта, много смисли

uint32–
int32–
float32–
текст (Latin-1)–
Как програмите разпознават файловете

Магически числа

Първите байтове на файла казват какъв е той, независимо от разширението.

ФорматПърви байтовеКато текст
PNG картинка89 50 4E 47‰PNG
JPEG снимкаFF D8 FFÿØÿ
PDF документ25 50 44 46%PDF
ZIP, DOCX, XLSX, PPTX50 4B 03 04PK…
Програма за Windows (.exe)4D 5AMZ
Нашият 3D модел53 37 4D 46S7MF

PK са инициалите на Phil Katz, създателя на ZIP. MZ са на Mark Zbikowski, един от авторите на MS-DOS.

Изненадата

Word файлът е ZIP архив

Започва с PK. Преименувай урок.docx на урок.zip и го отвори:

Текстът е в XML, картинките са отделни файлове, стиловете също. Excel и PowerPoint са устроени по същия начин.

Форматът е контейнер: архив, в който всяка част има свое място и своя договорка.

урок.docx (всъщност ZIP) ├─ [Content_Types].xml ├─ _rels/ ├─ docProps/ │ └─ core.xml ← автор, дати └─ word/ ├─ document.xml ← текстът ├─ styles.xml └─ media/ └─ image1.png
Общата идея

Заглавна част + блокове

Почти всички двоични формати са подредени по един и същи начин:

подпис
заглавна част
блок: тип · размер · данни
блок …
блок …

S7M

тип (2) · размер (4) · stride (4) · етикет (4) · данни · подравняване до 16

PNG

дължина (4) · тип (IHDR, IDAT…) · данни · контролна сума (4)

Защо размерът е преди данните? За да може програмата да прескочи блок, който не познава. Така по-стара програма чете и по-нов файл.

Алгоритъмът

Четене блок по блок

while (r.BaseStream.Position < r.BaseStream.Length)
{
    ushort type = r.ReadUInt16();
    r.ReadUInt16();                          // размер ÷ 8, не ни трябва
    uint  size = r.ReadUInt32();
    uint  stride = r.ReadUInt32();
    string tag = ReadFixedString(r, 4);
    long start = r.BaseStream.Position;

    switch (type) { /* 1 върхове · 4 индекси · 6 текстове · 7 части */ }

    r.BaseStream.Position = start + size;    // прескачаме до края
    Align(r, 16);                          // и до кратно на 16
}

Непознатите блокове просто се прескачат. Програмата не се чупи, когато срещне нещо ново.

Наградата

Данните вече са твои

{
  "positions": [195.4, -48.4, 112.6, …],
  "uvs": [0.264, 0.757, …],
  "indices": [1987, 1988, 1989, …],
  "parts": [
    { "name": "windmill",
      "start": 0, "count": 10602 },
    …
  ]
}

Щом байтовете станат масиви, можеш да правиш с тях каквото поискаш:

  • да ги покажеш с Three.js
  • да ги запишеш като .obj за Blender
  • да пресметнеш площ и обем
  • да оцветиш всяка част различно
  • да завъртиш колелото на мелницата

Това е усещането, заради което хората стават програмисти: нещо, което беше черна кутия, вече е под твой контрол.

Какво научи

Отвъд един 3D модел

  • Как паметта и файловете пазят данни
  • Защо има типове и как се избират
  • Знак, допълнителен код, endianness
  • Как са устроени файловите формати
  • Как се пише устойчив четец
  • Как данните се преобразуват (JSON)
  • Как се стига до визуализация
  • Как се мисли като изследовател: хипотеза → проверка

И една граница: разглеждаме от любопитство и за учене. Чуждите модели и файлове не се разпространяват.

Следващата стъпка

Какво още можеш
да отвориш?

Вземи произволен файл от компютъра си: снимка, песен, запис от игра. Отвори го в шестнайсетичен редактор. Познаваш ли подписа? Можеш ли да намериш размера му вътре?