Я разрабатываю реализацию сжатия Хаффмана в x64 MASM.Моя основная функция в синтаксисе C будет выглядеть следующим образом:
void* huffCompress(void* lpDataStream, unsigned long long qwLength);
Я использую соглашение Microsoft Fastcall, в котором параметры передаются вызываемой функции с использованием RCX, RDX, R8 и R9 (все остальное находится в стеке).
Я написал код, который генерирует массив размером 256 * 3.Каждый 3 байта состоит из:
as STRUCT
word wFreq
byte bSymbol
as ENDS
Затем код дважды перебирает lpDataStream.
Инициализация bSymbol с индексом в массиве
Увеличение wFreq для каждого байта
В приведенном ниже коде RBX - указатель на базу массива, RSI - указатель на lpDataStream, а RCX - qwLength.RAX должен быть 0 перед вводом кода ниже.
_populateArray:
lodsb
lea rdx, qword ptr[rbx+rax*04h]
sub rdx, rax
inc word ptr[rdx]
loop _populateArray
Затем функция выполняет итерацию по массиву, и для каждого элемента, у которого есть wFreq, который не равен нулю, она вычитает 13h (19 байт) из стека.Затем эти 19 байтов заполняются в соответствии со следующей структурой.
nl STRUCT
qword pFLink
qword pBLink
dword dwFreq
byte bSymbol
nl ENDS
Первые два слова являются прямой и обратной ссылками на следующий и предыдущий элементы в связанном списке.
xor rax, rax
mov r10, rsp
mov rcx, rax ;rcx = pFLink
mov rdx, rax ;rdx = pBLink
_generateLinkedList:
cmp word ptr[rbx+rax], 0000h
je _notInitialised
sub rsp, 13h
;write and setup pBLink for next entry
mov qword ptr[rsp+pBLink], rdx
mov rdx, rsp
mov r8w, word ptr[rbx+rax]
mov r9b, byte ptr[rbx+rax+02h]
mov word ptr[rsp+wFreq], r8w ;write dFreq to linked list
mov byte ptr[rsp+bSymbol], r9b ;write bSymbol to linked list
cmp rcx, 00h ;if pFLink is not initialised it means this is the first entry
je _firstEntry
mov qword ptr[rsp+13h], rsp ;when rcx != 00h it means that there is an entry before this one "before" on stack remember
_firstEntry:
mov rcx, rsp
_notInitialised:
add rax, 03h
cmp rax, 300h
jna _generateLinkedList
Приведенный выше код работает по желанию, я добавил его для полноты.RBX все еще указывает на массив.
Затем функция запускает пузырьковую сортировку в результирующем связанном списке, сортируя в порядке возрастания.Это означает, что элемент без pBLink (без обратной ссылки) имеет самый низкий wFreq.Это не круговой двусвязный список.
Следующим шагом реализации сжатия Хаффмана является создание узла с wFreq, равным сумме двух низших частот.
Мой план для этогонужно было сделать следующее:
Сложить вместе два наименьших значения wFreq
Сделать pFLink в самом нижнем элементе NULL
Сделать pFLink и pBLink вторым самым низким (pHead-> pFLink) NULL
Сделать больше места в стеке (19 байт) и добавить узел в конец (это включает в себя поиск элемента с NULL pFLink и замену его на новый узел.Кроме того, новый узел имеет wFreq двух младших, добавленных вместе.
Это гдепроблема в том. Мне нужно, чтобы pFLink и pBLink нового узла указывали на два нижних элемента (узлы, у которых были указатели NULLED на этапах 2 и 3. Однако если я это сделаю, то новый узел не сможет подключитьсяв связанный список.
РЕДАКТИРОВАТЬ: Я думаю, что вышеупомянутая опция будет работать, мне придется переработать алгоритм сортировки так, чтобы при добавлении нового узла и его сортировке он вставлялся между элементами.Код понял бы, что нашел «новый узел», потому что pBLink не будет корректным.Тогда он узнает, что следующий элемент находится прямо «над» (на 19 байт над «новым узлом»).Я думаю, что это можно сделать во время создания нового узла, поскольку новому узлу не нужно , чтобы поместить его в новое пространство в стеке, его можно поменять местами с элементом, который находится в нужном месте.Это грязный обходной путь, если есть лучший способ, который я бы хотел услышать.
У меня была идея, что когда функция сортировки находит узел, где pBLink не указывает на предыдущий элемент, он должен простопередвинуть следующий элемент, вычтя 13h из его указателя.Это не сработало, потому что новые узлы (созданные путем сложения двух самых низких частот) могут быть где угодно после сортировки.
Есть ли способ преодолеть это, не добавляя еще два слова в структуру nl?