Десериализация в Haskell: парсинг карт TacOps
Введение⌗
Предположим, мы читаем двоичную последовательность из файла (или слушаем на проводе) и хотим преобразовать её в некоторую осмысленную структуру. Для этого нам нужен парсер – вычислительный процесс, который, грубо говоря, разобъёт бездушную последовательность единиц и нулей на несущие смысл компоненты и сконструирует из них нашу структуру.
И наоборот, мы хотим сохранить известную структуру данных на диск (например, для последующего архивирования) или передать по сети другому компьютеру. Нам нужно провести обратную операцию – анпарсинг, т.е. преобразовать структуру в последовательность единиц и нулей.
В обоих случаях мы бы хотели, чтобы правила (т.н. грамматика) парсинга и анпарсинга для одной и той-же структуры были согласованы (например, если б это было не так, то записанный на флэш-карту процессором цифрового фотоаппарата файл JPEG был бы нечитаем на других компьютерах).
В комплекте с Haskell идёт замечательный пакет binary, который предоставляет монады Get и Put, а также комбинаторы для высокопроизводительной (1 G/s) десериализации
и сериализации двоичных данных в/из типов Haskell. Ветку модулей Data.Binary я использовую для создания Haskell-бииблиотеки чтения/записи игровых карт программы TacOps (файлов с расширением .dat).
Представление местности TacOps на Haskell⌗
Формат карты TacOps – это проприетарный, закрытый формат, о котором ничего не известно. Однако, некоторое время назад я сделал попытку его реверс-инженеринга и выложил
спецификацию на GitHub. Вкратце о формате .dat: заголовок с информацией (в частности, о
количестве горизонтальных и вертикальных локаций) и блок с последовательными описаниями локаций карты (по два байта на ячейку).
Для начала смоделируем общие особенности местности: высоты, мобильность, лес, город и т.д. Я использую для них те-же названия, что и в самой TacOps: например, E1
означает “первый уровень высоты” (в противопоставление нулевому), NOGO2 – непроходимость для колёсной и гусеничной техники, Losblock – непроходимость линии визирования (оптического и тепловизионного) и т.д.
module TacopsTerrain where
data PrimaryTerrain = Clear
| NOGO1 -- no-go for wheeled
| NOGO2 -- no-go for wheeled & tracked
| NOGO3 -- no-go for vehicles & dismounts
| Rough1
| Rough2
| Rough3
| Rough4
| Water
deriving (Eq, Show)
data SecondaryTerrain = Losblock
| Road
| Woods
| Town
deriving (Eq, Show)
data Elevation = E0 | E1 deriving (Eq, Show)
Теперь опишем тип самой игровой карты TacOps, а также тип одной локации (ячейки) на карте.
data DatMap = DatMap
{ mapNum :: Int
, mapWidth :: Int
, mapHeight :: Int
, mapBmpWidth :: Int
, mapBmpHeight :: Int
, mapEasting :: Int
, mapNorthing :: Int
, mapVersion :: Int
, mapName :: String
, mapCells :: [DatCell]
} deriving (Show)
data DatCell = DatCell
{ cellPri :: PrimaryTerrain
, cellSecs :: [SecondaryTerrain]
, cellElev :: Elevation
} deriving (Show)
Как видно (и это указано в моей спеке на гитхабе), значений типа SecondaryTerrain в одной локации может быть несколько (например, дорога и лес).
Тайпкласс Binary⌗
Тайпкласс Binary объединяет все типы, которые (де)сериализабельны. Чтобы уметь читать и писать карты из .dat-файлов, нам всего-навсего потребуется реализовать интерфейс
Binary для нашей структуры DatMap (это наша репрезентации игровой карты TacOps).
Необходимый интерфейс Binary:
class Binary t where
put :: t -> Put -- encode a value in the Put monad
get :: Get t -- decode a value in the Get monad
Монады Get t и Put это монады состояния входного (выходного) бинарного потока. Монадическое связывание предоставляет подобие read-only и write-only контекстов для
парсинга и анпарсинга соответственно.
Данные потребляются и автоматически изымаются из входной последовательности в монаде Get. Все комбинаторы начинаются на слово get, le и be означает little и
big endian, соответственно, цифры означают количество битов в машинных словах, getByteString читает произвольную последовательность в крутейший тип ByteString.
Пример Get монады (парсера):
hdr <- getWord16le
skip 1
payload <- getByteString 79
cksum <- getWord32le
Напротив, в монаде Put бинарные данные автоматически наращиваются комбинаторами put*:
putWord16le 280
putWord8 0
putLazyByteString payload
putWord8 0
И так далее. Познакомиться с чудесными модулями Data.Binary.Get и Data.Binary.Put можно на Hackage.
Итак, напишем интерфейс к Binary! А Haskell позаботиться обо всём остальном, чтобы мы могли читать и писать игровые карты TacOps.
Ввиду динамичности SecondaryTerrain в одной локации, мы для удобства и простоты чтения кода напишем по три вспомогательные функции для наших парсера и анпарсера:
- Преобразование между двумя байтами (“Flags byte” и “Terrain byte”, как я назвал их в спеке) и типом
DatCell– нашей репрезентации локации на карте - (Де)кодирование одной ячейки
DatCell - (Де)кодирование списка ячеек, т.е.
[DatCell]
Десериализатор структуры DatMap⌗
Довольно прямолинейный парсинг, который просто проскакивает неизвестные поля заголовка файла (формат проприетарный…):
instance Binary DatMap where
get = do
num <- getWord16le
skip 4
width <- getWord16le
height <- getWord16le
skip 4
bmpwidth <- getWord16le
bmpheight <- getWord16le
skip 32
easting <- getWord16le
northing <- getWord16le
version <- getWord16le
name <- getLazyByteString 7
skip 1 -- the C-string's \NULL byte
cells <- getRemainingLazyByteString
return $ DatMap
(f num)
(f width)
(f height)
(f bmpwidth)
(f bmpheight)
(f easting)
(f northing)
(f version)
(BL8.unpack name)
(runGet decodeCells cells)
where
f = fromEnum
Парсер в конце использует наш подпарсер decodeCells для парсинга собственно длиннющего хвоста файла (в котором-то и находятся ячейки). Тот, в свою очередь, опирается на
парсинг всего одной ячейки-локации (функция decodeCell).
decodeCells :: Get [DatCell]
decodeCells = do
e <- isEmpty
case e of
True -> return []
False -> do
dc <- decodeCell
dcs <- decodeCells
return (dc:dcs)
decodeCell :: Get DatCell
decodeCell = do
secsb <- getWord8
prib <- getWord8
return $ (bytesToDatCell prib secsb)
Последняя функция, в свою очередь, использует bytesToDatCell для конструирования локации datCell из “сырых” байтов:
bytesToDatCell :: Word8 -> Word8 -> DatCell
bytesToDatCell prib secsb = DatCell pri secs elev
where pri = case prib of
0x00 -> Clear
0x01 -> NOGO1
0x02 -> NOGO2
0x04 -> NOGO3
0x08 -> Rough1
0x10 -> Rough2
0x18 -> Rough3
0x20 -> Rough4
0x30 -> Water
_ -> Clear -- Stay safe from occasional "junk" on the edges of some maps
elev = case (secsb .&. 0x08) of
0 -> E0
0x08 -> E1
secs = f secsb
f b | b .&. 0x02 == 0x02 = [Losblock] ++ f (b `xor` 0x02)
f b | b .&. 0x20 == 0x20 = [Road] ++ f (b `xor` 0x20)
f b | b .&. 0x40 == 0x40 = [Woods] ++ f (b `xor` 0x40)
f b | b .&. 0x80 == 0x80 = [Town] ++ f (b `xor` 0x80)
f b | otherwise = []
Здесь мы применяем обычные логические операции над битовыми масками для заглядывания “внутрь” байта “первичных” и байта “вторичных флагов” локации. При этом, в файле двухбайтовая ячейка лежит “вторичным” байтом вперёд.
Сериализатор структуры DatMap⌗
Продолжаем описание instance Binary DatMap. Нам нужно написать put t где t это наша структура. Вот наш анпарсер:
put (DatMap n w h bmpw bmph ea no ver name dcs) = do
putWord16le (toEnum n)
replicateM_ 4 $ putWord8 0
putWord16le (toEnum w)
putWord16le (toEnum h)
replicateM_ 4 $ putWord8 0
putWord16le (toEnum bmpw)
putWord16le (toEnum bmph)
replicateM_ 6 $ putWord8 0
putWord16le (toEnum bmpw)
putWord16le (toEnum bmph)
replicateM_ 22 $ putWord8 0
putWord16le (toEnum ea)
putWord16le (toEnum no)
putWord16le (toEnum ver)
putLazyByteString (BL8.pack (take 7 name)) -- take only 7 characters
putWord8 0 -- C-string \NULL
encodeCells dcs
Входной тип DatMap деконструируется на составные части паттерн-матчингом Haskell. Мы затем начинаем последовательно и нудно писать эти части в поток; код почти-что
зеркален с методом get. Перед блоком с ячейками идёт семисимвольное имя карты (так, видимо, когда-то решил разработчик..) и мы должны быть аккуратны, чтобы
случайно не вписать туда сколь угодно длинную строку из нашего типа String (который мы используем для репрезентации). После семи ASCII символов мы любезно кладём нуль,
чтобы удовлетворить концепцию строк в языке Си. Комбинатор replicateM_ повторяет монадическое выражение n раз и не собирает результат.
encodeCells :: [DatCell] -> Put
encodeCells dcs= do
foldM_ (\_ dc -> encodeCell dc) () dcs
encodeCell :: DatCell -> Put
encodeCell dc = do
let (prib, secsb) = datCellToBytes dc
putWord8 secsb
putWord8 prib
datCellToBytes :: DatCell -> (Word8, Word8)
datCellToBytes (DatCell pri secs elev) = (prib, secsb)
where prib = case pri of
Clear -> 0x00
NOGO1 -> 0x01
NOGO2 -> 0x02
NOGO3 -> 0x04
Rough1 -> 0x08
Rough2 -> 0x10
Rough3 -> 0x18
Rough4 -> 0x20
Water -> 0x30
bits = foldr (\s acc -> f s .|. acc) 0x00 secs
f Losblock = 0x02
f Road = 0x20
f Woods = 0x40
f Town = 0x80
secsb = case elev of
E0 -> bits
E1 -> bits .|. 0x08
Проверка⌗
Теперь мы можем считывать и записывать .dat карту TacOps из битового потока с помощью операций:
encode :: Binary a => a -> ByteString
decode :: Binary a => ByteString -> a
и других функций из Data.Binary вроде decodeFile.
Пример чтения карты из файла (я подставляю пустой список, чтобы не выводить на экран длиннющий список локаций):
λ> d <- decodeFile "../Map003c.dat" :: IO DatMap
λ> show d{mapCells =[]}
"DatMap {mapNum = 3, mapWidth = 74, mapHeight = 54, mapBmpWidth = 731, mapBmpHeight = 531, mapEasting = 0, mapNorthing = 0, mapVersion = 300, mapName = \"Map003c\", mapCells = []}"
Пример сохранения карты в файл:
λ> BL.writeFile "../Map003c_my.dat" (encode d)
λ> d' <- decodeFile "../Map003c_my.dat" :: IO DatMap
λ> d == d'
True
Видно, что считанная из оригинального .dat-файла и считанная из созданного нами .dat-файла карты эквивалентны. Вот и всё что требуется для поддержки карт TacOps!
Код /= документация⌗
Как нетрудно догадаться, следующее уравнение всегда должно выполнятся для нормальных экземпляров класса Binary:
decode . encode == id
Мы можем показать, что это так, в том и только в том случае, если и запись и чтение данных производятся с использованием одной и той-же спецификации (описания формата файла).
Поскольку TacOps – это программа с закрытым исходным текстом, мне многое неизвестно о других полях в заголовке .dat-файла. При чтении из файла я просто проскакиваю
неизвестные байты, и это не мешает работе – вся информация из карты отображается корректно в репрезентации. Однако, это также означает, что я и не могу записать данные в
эти неизвестные поля заголовка файла, а значит уравнение выше не выполняется.
Надо бы проверить, читает ли стандартный редактор карт TacOps (под Windows) сериализованные моим кодом карты… Думаю, что да.
Напоминание всем поклонникам кодовой политики ядра Linux: исходный код не является надлежащей документацией к закрытому протоколу или формату файла.