Huffman Compression

Hi,

I am new to the forum, and wishing I found it earlier to be honest, but here goes.

I am currently trying to write a Heap.asm and Huffman.asm for a project, but have no idea where to start.
(Using NASM on Ubuntu, Intel 32bit processor)
Basically all I was given is the 2 Skeleton files:

Heap.asm
--------------------------------------------------------------------------------------------------------------
;*****************************************************************************
void heap_initialize(heap *H)
;*****************************************************************************

;*****************************************************************************
void heap_insert(heap *H, heap_node *node)
;*****************************************************************************

;*****************************************************************************
void heap_remove(heap *H, heap_node *node)
;*****************************************************************************

--------------------------------------------------------------------------------------------------------------

Huffman.asm
--------------------------------------------------------------------------------------------------------------
;*****************************************************************************
void huffman_build_tree(heap *h, heap_node **t)
;*****************************************************************************

;*****************************************************************************
void huffman_initialize_table(huffman_node *t)
;*****************************************************************************

;*****************************************************************************
void huffman_build_table(heap_node *root, huffman_node *t, int code, int size)
;*****************************************************************************

--------------------------------------------------------------------------------------------------------------

I have written a delete node for a binary tree, but not too sure how to do it for the heap.

;*****************************************************************************
void delete_node(node **root, char *name);
;*****************************************************************************
%define root
%define name
%define n
%define temp

delete_node:
push ebp
mov ebp, esp
sub esp, 8

mov edx, root
mov ebx, root
mov edx,
cmp edx, 0 ; if (*root != NULL) {
jz near .done

cld
mov ecx, 32
mov esi, name
mov edi, edx

.while: ; if (strcmp(name, (*root)->name) < 0)
lodsb
scasb
jl .if
jg .else_1
cmp al, 0
jz .else_2
dec ecx
jnz .while
jmp .else_2

.if:
push dword name
lea ebx,
push ebx
call delete_node ; delete_node(&(*root)->left, name);
add esp, 8
jmp .done

.else_1: ;
push dword name ;if (strcmp(name, (*root->name) > 0)
lea ebx,
push ebx
call delete_node ;delete_node(&(*root)->right, name);
add esp, 8
jmp .done

.else_2:
push edx ;temp = *root;
cmp dword , 0 ;if ((*root)->left == NULL)
jnz .else_3
mov ecx,
mov , ecx ;*root = (*root)->right;
jmp .free

.else_3:
cmp dword , 0 ;if ((*root)->right == NULL) {
jnz .else_4
mov ecx,
mov , ecx ;*root = (*root)->left;
jmp .free

.else_4:
lea ecx, n
push ecx
lea ecx,
push ecx
call remove_max ;remove_max(&(*root)->left, &n);
add esp, 8
mov edx, root
mov esi,
mov ebx, n
mov ecx,
mov , ecx ;n->left = (*root)->left;
mov ecx,
mov , ecx ;n->right = (*root)->right;
mov , ebx ; *root = n;

.free:
call free ;free(temp);
add esp, 4

.done:
mov esp, ebp
pop ebp
ret

Any and all help would be appreciated.
~Thanks

Posted on 2010-10-21 08:41:15 by Kevz

Re: Huffman Compression

Kevz,

Some comments:

use recursion only as a last resort � iteration is better memory-wise;

meaningful labels can somewhat remedy lack of comments;

structure node has to be defined, not reverse-engineered or guessed from things like ;

near operator in jz near .done forces it to have 6-byte encoding; NASM can decide optimal jump type if you allow it to have multiple passes with -O option;

%defines for arguments probably should specify size together with address: %define root dword ;

misleading comment is much worse than no comment at all: if (strcmp(name, (*root->name) > 0) has missing closing parenthesis (it's just an example, there are more to it in the source);

0x80 is less than 0, but it's above 0;

heap as a data structure doesn't manifest the same property as a tree (indeed it's quite contrary: for any heap node its childs' keys aren't greater than this node's key);

enforce zero-padding of the key, then repe cmpsb can be useful;

delete_node() looks like using cdecl calling conventions, yet it tampers ebx, esi and edi;

how could free() guess the address of memory block to free?

As I said above, heap node's childs are not greater than it. Keeping this property in mind, it's easy to implement basic operations on heap (if you don't care about it being imbalanced).

Posted on 2010-10-21 10:33:06 by baldr

Re: Huffman Compression

Thanks for the advice baldr, still new and always learning on the Assembly Scene.

Posted on 2010-10-21 12:29:09 by Kevz

ASM Community