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
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
Thanks for the advice baldr, still new and always learning on the Assembly Scene.
Posted on 2010-10-21 12:29:09 by Kevz