16. TOS23

Вы работаете в стартапе ITTerra, который собирается выпустить на рынок новую операционную систему TerraOS. Специально для неё в компании разработали файловую систему TOS23. Вам нужно написать принципиально новую реализацию fsck для этой файловой системы, чтобы проверить, что система в порядке.

TOS23 представляет собой большой однонаправленный кольцевой буфер. Однонаправленным кольцевым буфером называется последовательность блоков, последний блок которой указывает на первый. Блок делится на три секции. Размер первой секции — 4 байта, в ней хранится размер секции данных. Компьютер хранит числа, записывая байты в обратном порядке. Это значит, что последовательность байтов 0x03 0x00 0x00 0x00 является числом 3 в десятичной системе счисления. Далее следует секция данных, её размер варьируется и указывается в первой секции. И последняя, третья секция имеет размер 4 байта и указывает индекс следующего блока данных. Заметим, что индексация начинается с 0 и ведётся от начала кольцевого буфера.

Вам необходимо проверить, что:

• система представляет собой кольцевой буфер: начиная в 0-м блоке и пройдя по всему буферу, мы должны вернуться в начальную точку;
• нет потерянных блоков: каждый байт нашей системы принадлежит какому-то блоку в этом буфере.

Первичным является тест на кольцевой буфер. Если он не пройден, вы должны вывести not a ring buffer. Затем, если система является кольцевым буфером, необходимо проверить, что нет потерянных блоков, и вывести data loss, если таковые имеются. В противном случае система в порядке и надо вывести OK. Таблица записана в файл, по которому можно перемещаться как угодно. Модифицировать файл нельзя. Максимальный размер файла — 128 МБ.

Имя файла, в котором записана таблица размещения, например table1.taf23.

• OK — если оба условия выполнены;
• not a ring buffer — если файл не представляет собой кольцевой буфер;
• data loss — если есть потерянные блоки.

Файл примера можно по ссылке ниже:

https://disk.yandex.ru/d/DEvQ9_yFJEW-ZQ