Huffman Coding Using Doubly Linked List

Question

I am developing an implementation of Huffman Compression in x64 MASM. My main function in C syntax would be:

void* huffCompress(void* lpDataStream, unsigned long long qwLength);

I am using Microsoft's Fastcall convention where the paramters are passing to the called function using RCX, RDX, R8 & R9 (anything else is on the stack).

I have written code which generates an array of size 256*3. Each 3 byte consists of:

as STRUCT
    word wFreq
    byte bSymbol
as ENDS

The code then iterates over the lpDataStream twice.

1. Initialising bSymbol with the index in the array

2. Incrementing wFreq for each byte

In the code below RBX is a pointer to the base of the array, RSI is a pointer to the lpDataStream and RCX is qwLength. RAX needs to be 0 before entering the below code.

_populateArray:
    lodsb
    lea rdx, qword ptr[rbx+rax*04h]
    sub rdx, rax
    inc word ptr[rdx]
loop _populateArray

The function then iterates over the array and for each element which has a wFreq which is not zero it subtracts 13h (19 bytes) from the stack. These 19 bytes are then populated as per the following structure.

nl STRUCT
    qword pFLink
    qword pBLink
    dword dwFreq
    byte  bSymbol
nl ENDS

The first two qwords are forward and backward links to the next and previous elements in the linked list.

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

The above code works as desired, I have added it for completeness. RBX is still pointing to the array.

The function then runs bubble sort on the resulting linked list, sorting in ascending order. This means the element with no pBLink (no backward link) has the lowest wFreq. It is not a circular doubly linked list.

The next step of implementing Huffman Compression is to create a node with a wFreq equal to the sum of the two lowest frequencies.

My plan for this was to do the following:

1. Add the two lowest wFreq values together

2. Make pFLink in the lowest element NULL

3. Make both pFLink and pBLink is the second lowest (pHead->pFLink) NULL

4. Make more stack space (19 bytes) and add a node to the end (this involves finding the element with a NULL pFLink and changing it to the new node. Additionally the new node has the wFreq of the two lowest added together.

This is where the problem is. I need to make the pFLink and pBLink of the new node point to the two lowest elements (The nodes which had their pointers NULLED in step 2 & 3. However if I do this then the new node cannot be connect to the linked list.

EDIT: I think the above option would work, I would have to rework the sorting algorithm so that when a new node is added and needs to be sorted it is inserted inbetween elements. The code would realise it has found a "new node" because the pBLink wouldn't be correct. It would then know the next element is directly "above" (19 bytes above the "new node"). I think this could be done during the new node creation as the new node doesn't need to be placed in the new space on the stack it can be swapped with the element which is at it's desired place. It's a dirty workaround, if there is a better way I would love to hear it.

I had the idea that when the sorting function finds a node where the pBLink doesn't point to the previous element it should just move up the next element by subtracting 13h from it's pointer. This didn't work because the new nodes (those created by adding the two lowest frequencies together) could be anywhere after sorting.

Is there any way to overcome this without adding two more qwords to the nl structure?

Answer 1

If you are interested in speed, then you need to start with carefully considered algorithm choices before even remotely considering writing it in assembler. The correct choice of algorithms will make order of magnitude improvements. Then writing it in assembler may give you small factor improvements.

In particular you need a much better choice for sorting, likely quicksort in this case, and you can do the Huffman coding much more simply, in place, without re-sorting linked lists.