Описание формата ACM. v1.0, 18.06.2000 ======================= ВНИМАНИЕ: Формат ACM является собственностью Interplay, как указано в различных документах, сопровождающих их игры. Замечание1: Данный документ представляет собой всего лишь попытку описания моего понимания формата на данный момент, по этой причине названия переменных и структур являются чисто условными. Их реальное назначение может оказаться совершенно другим. Замечание2: В настоящий момент я не могу объяснить алгоритм распаковки, так что мне приходится ссылаться на исходники распаковщика. Замечание3: В описании используются следующие целые типы: DWORD 32-битное знаковое целое WORD 16-битное знаковое целое Кроме того используются C-подобные объявления и выражения. ACM-файл состоит из двух основных частей: 1. короткий заголовок 2. ACM-Поток, содержащий запакованную информацию 1. Заголовок. --------------- Следующая таблица описывает назначение полей заголовка: число битов | Значение | Описание -------------+---------------------+----------------- 24 | 0x97 0x28 0x03 | ACM-signature1 8 | 0x01 | ACM-signature2 32 | число сэмплов | сэмпл - это 16 битов 16 | число каналов | 1-моно, 2-стерео (реально не используется) 16 | частота (bitrate) | 22050 во всей известных ACM (реально не используется) 4 | packAttrs | (см. ниже) 12 | packAttrs2 | Пояснение: I. Первые 4 байта любого ACM-файла содержат 0x01032897 - это что-то вроде сигнатуры; расшифровка значений не известна. Учитывая, что Sig1 и Sig2 читаются из файла по отдельности, можно предположить, что Sig1 является действительной сигнатурой ACM, тогда как Sig2 представляет собой, например, номер версии ACM. II. В ACM-файле указаны число каналов и частота, однако эти значения не используются в тех играх, которые мне известны (Fallout1, Fallout2 и Planescape). Частота всех известных в настоящий момент файлов - 22050 Гц. Число каналов - 1 или 2, но действительное число каналов зависит от использования сэмплов. III. Следующие два значения определяют поведение алгоритма распаковки. packAttrs обозначает уровень рекурсии при обработке пакованных данных, если это значение равно 0, распаковка не производится. packAttrs2 - это число подблоков в запакованном блоке Packed-Block (см. пункт 2). Действия: I. На основе значений из заголовка определяются следующие переменные (их имена соответствуют именам в исходниках): a) someSize = 1 << packAttrs (размер одного подблока) b) someSize2 = someSize * packAttrs2 (размер одного PackedBlock) c) decBuff_size = 3*someSize/2 - 2 (размер буфера "памяти"), это значение представляет собой сумму следующей геометрической прогрессии: 2 + 4 + 8 +...+ ( 1 << (packAttrs-1) ) плюс ( 1 << (packAttrs-1) ) еще раз. II. Создаются следующие массивы (их имена отличаются от исходников): a) PackedBlock = DWORD [someSize2] (соответствует массиву someBuff). Этот массив удобнее рассматривать как массив переменной длины DWORD [packAttrs2][someSize] или DWORD [cnt_of_blocks][block_len]. Используется для обработки пакованных данных. b) если packAttrs не равно 0, создается и инициализируется нулями массив MemoryBuffer = DWORD [decBuff_size] (соответствует массиву decompBuff). Его можно рассматривать, как следующую структуру: { WORD [someSize/2][2], DWORD [someSize/4][2], DWORD [someSize/16][2], ... DWORD [1][2] } Каждый элемент используется на соответствующем уровне рекурсии. Используется для "склейки" последовательных PackedBlock'ов при распаковке. c) AmplitudeBuffer = WORD [0x10000], и Buff_Middle = &litudeBuffer[0x8000], последний используется как массив WORD'ов с индексами от -0x8000 до 0x7FFF. Буфер заполняется амплитудами, применяемыми при распаковке. 2. ACM-Поток. --------------- Представляет собой поток битов. Организован в виде набора битовых блоков, каждый из которых может при распаковке дать someSize2 сэмплов, т.е. один PackedBlock. Назовем один битовый блок BitBlock. Тогда ACM-Поток - это просто последовательность BitBlock'ов (различной длины). Каждый BitBlock содержит информацию об амплитудах, использующихся в соответствующем PackedBlock, а также "описание" действий над этими амплитудами для получения сэмплов. I. Первые 20 битов BitBlock'а можно рассматривать как заголовок блока: биты | имя ------+------ 4 | pwr 16 | val Используя эти значения AmplitudeBuffer заполняется следующим образом: count = 1 << pwr Buff_Middle [+0] = 0 Buff_Middle [+1] = val Buff_Middle [+2] = 2*val ... Buff_Middle [+(count-1)] = (count-1)*val Buff_Middle [-1] = -val Buff_Middle [-2] = -2*val ... Buff_Middle [-count] = -count*val II. PackedBlock заполняется значениями из AmplitudeBuffer'а. Что производится при помощи специальных функций заполнения (Filler'ов). Имеется 14 разных Заполнялок (описание будет дано чуть ниже): Zero, Ret0, Linear, k13, k12, t15, k24, k23, t27, k35, k34, k45, k44 и t37. Каждый (или почти каждый) Filler предназначен для заполнения только одного столбца PackedBlock'а, который рассматривается как DWORD[packAttrs2][someSize] (n-ный столбец в этом случае является массивом { PB[0][n], PB[1][n], ... , PB[pa2-1][n] }). Для каждого из столбцов вызывается один из Заполнителей. Для выбора этого Заполнителя из БитБлока считываются 5 битов, и это 5-битное значение используется как индекс в следующем массиве: Filler[32] = {Zero, Ret0, Ret0, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, Linear, k13, k12, t15, k24, k23, t27, k35, k34, Ret0, k45, k44, Ret0, t37, Ret0, Ret0}; Заполнителю передаются два параметра: его индекс в массиве и номер столбца, к которому Заполнитель применяется. Таким образом, заполнение PackedBlock'а амплитудами можно представить следующим C-псевдокодом: for (int i=0; i 2bits | индекс в B_M --------------+----------- | -------+-------------- 0 | 0, 0 | 0,0 | -3 1,0 | 0 | 1,0 | -2 1,1,0,0 | Buff_Middle [-1] | 0,1 | +2 1,1,0,1 | Buff_Middle [+1] | 1,1 | +3 1,1,1, 2bits | (*) -------------/ 9) k34. До 4-х битов: биты | значение /----> 2bits | индекс в B_M ------------+----------- | -------+-------------- 0 | 0 | 0,0 | -3 1,0,0 | Buff_Middle [-1] | 1,0 | -2 1,0,1 | Buff_Middle [-1] | 0,1 | +2 1,1, 2bits | (*) -------------/ 1,1 | +3 10) k45. До 5 битов: биты | значение -------------+----------- 0 | 0, 0 1,0 | 0 1,1, 3bits | 3bits->индекс в B_M: 000-> -4, 100-> -3, 010-> -2, 110-> -1 001-> +1, 101-> +2, 011-> +3, 111-> +4 11) k45. До 4-х битов: биты | значение -----------+----------- 0 | 0 1, 3bits | 3bits->индекс: 000-> -4, 100-> -3, 010-> -2, 110-> -1 001-> +1, 101-> +2, 011-> +3, 111-> +4 12) t15. Берет 5 битов из БитБлока. Это значение рассматривается как трехзначное число в троичной системе исчисления. Каждая из цифр используется как индекс в Buff_Middle. Таким образом, заполняются три последовательных элемента столбца. 13) t27. Читает 7 битов и трактует их как трехзначное число в пятеричной системе. Каждая из цифр - это индекс в Buff_Middle, то есть получаем 3 последовательных элемента в столбце. 14) t37. Берет 7 битов и рассматривает из значение как двузначное число в 11-ричной системе (и не надо смеяться, это действительно так). Цифры используются как индексы в Buff_Middle; получаем два последовательных элемента столбца. IV. Обработка данных в PackedBlock'е. Если packAttrs равно 0, больше ничего не нужно делать - мы уже получили в PackedBlock звуковые сэмплы. В противном случае нужно применить к значениям из PackedBlock алгоритм распаковки. Это происходит в функциях unpackValues, sub_4d3fcc и sub_4d420c (см. исходники). Все, что я могу сообщить об алгоритме, это то, что он рекурсивный. Во время распаковки PackedBlock рассматривается как DWORD [cnt_of_blocks][block_len]. В начале обработки cnt_of_blocks = packAttrs2*2 block_len = someSize/2. При переходе с одного уровня рекурсии на следующий cnt_of_blocks умножается на 2, а block_len делится на 2, таким образом значение cnt_of_blocks*block_len остается постоянным. Кроме того я могу описать некоторые свойства результатов обработки. Замечание: для изучения этих свойств алгоритм был несколько модифицирован: в функции unpackValues был закоментирован цикл for, выполняющий инкремент элементов PackedBlock'а. Этот инкремент просто добавлял постоянное значение ко всем элементам результирующего массива, так что он явно не является ядром алгоритма. Пусть F(PB) - результат применения упомянутых выше функций к PackedBlock'у PB. Обозначим PB{[i]=v} PackedBlock, в котором все элементы равны нулю, за исключением i-ого, которому присвоено значение v. То есть PB{[1]=5} обозначает массив {0,5,0,...,0}. F обладает следующими свойствами: 1) "Компактный носитель". F (PB{[i]=v}) равен нулю везде, кроме элементов от i до (i+2*someSize-1). 2) Периодичность с периодом someSize. F (PB{[i]=v}) и F (PB{i+someSize}=v) отличаются только тем, что последний сдвинут на someSize. 3) Линейность. F (PB{[i]=a, [j]=b}) = a*F (PB{[i]=1}) + b*F (PB{[j]=1}). 4) Почти ортогональность (эдакая странная). Обозначим f_i = F (PB{[i]=1}), где i=0..someSize-1. w_i = F (PB{ [i]=1, [i+someSize]=1, [i+2*someSize]=1, ... } ), сдвинутый влево на (2*someSize) элементов (то есть мы просто отбрасываем первые элементы). И группируем их индексы следующим образом: g0 = {0} g1 = {1} g2 = {2, 3} g3 = {4, 5, 6, 7} ... g_packAttrs = { ..., (someSize-1) } Тогда любые два вектора w_i и f_j ортогональны (в смысле скалярного произведения), если их индексы принадлежат различным группам. Более того, w_i и f_j, принадлежащие одной группе, ортогональны, когда i и j имеют различную четность (то есть один из них четный, тогда как другой нечетный). Возможно, w_i могут быть использованы как тестовые функции для проверки наличия в сигнале компонентов f_j.