Content deleted Content added
revert deleted implementations |
|||
Line 39:
==Implementations==
===[[C programming language|C]]===
/****************************************/
/*Author: Chiam Jia-Han a.k.a JellyWorld*/
/*Copyright: This code is distributed */
/*unconditionally. You may use it */
/*without author acknowledgement. */
/****************************************/
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
int source;
int dest;
int weight;
}Edge;
void BellmanFord(Edge edges[], size_t edgecount, size_t nodecount, size_t source)
{
int* distance = (int*) malloc(nodecount*sizeof(int));
for(int i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(int i = 0; i < nodecount; i++)
{
for(int j = 0; j < edgecount; j++)
{
if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight)
{
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for(int i = 0; i < edgecount; i++)
{
if(distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
{
printf("Error occured. Negative edge weight cycles detected");
break;
}
}
for(int i = 0; i < nodecount; i++)
{
printf("The shortest distance between nodes %i and %i is %i", source, i, distance[i]);
}
}
===[[Assembly programming language|Assembly (NASM)]]===
Program written by Chiam Jia-Han a.k.a JellyWorld
segment .model
segment .stack
segment .data
INFINITY dd 1
format_string1 db "Error occured. Negative edge weight cycles detected", 0
format_string2 db "The shortest distance between nodes %i and %i is %i", 0
extern _printf
extern _malloc
extern _exit
segment .bss
distance resd 1
segment .text
global _BellmanFord
_BellmanFord: ;Function takes in same parameters as C function above
mov eax, INFINITY ;Load Infinity into register eax
shl eax, 29 ;Shift register 29 bits left
mov dword [INFINITY], eax ;Define INFINITY as 2^29
push ebp ;Store ebp register in stack
mov ebp, esp ;Fix ebp to stack pointer
mov eax, [ebp+16] ;Store third parameter in eax
shl eax, 2 ;Bitshift it
push eax ;Push it onto stack as parameter for malloc
call _malloc ;Call malloc
pop edx ;Pop it back off the stack
shl eax, 2 ;Multiply return value by 4
mov dword [distance], eax ;Store pointer returned in distance
mov ecx, [ebp+16] ;Store nodecount in ecx
sub ecx, 1 ;Subtract one
loopend1: ;Start of loop
shl ecx, 2 ;Multiply by 4
lea eax, [distance+ecx] ;Store pointer in eax
shr ecx, 2 ;Divide by 4
cmp ecx, [ebp+20] ;Check for equality with source node
jnz dinf ;Jump to"else" clause if equality not detected
mov dword [eax], 0 ;Change value at pointer to 0
jmp end1 ;Go to end of loop
dinf: ;Else Clause
mov edx, [INFINITY] ;Store value in edx
mov dword [eax], edx ;Set value to infinity
end1: ;End of loop label
loop loopend1 ;Return to front of loop
mov ecx, [ebp+16] ;Reload nodecount into register eax
dec ecx ;Decrement ecx
loopend2: ;Start of loop label
mov ebx, 0 ;Set ebx to 0
innerloop1: ;Inner Loop label
mov edx, [ebp+12] ;Store edgecount variable in edx
cmp edx, ebx ;Compare for equality
jz end2 ;Skip to loop end if they are equal
mov eax, ebx ;Store ebx in eax
add eax, edx ;Add the registers
mov edx, [ebp+8] ;Load edge array into edx
push edx ;Store edx on the stack temporarily (mul instruction modifies edx)
push 12 ;Push 12 onto the stack
mul dword [esp] ;Multiply 12 with eax
add esp, 4 ;Pop 12 off the stack
pop edx ;Push it back off the stack
mov edx, eax ;Set edx to eax
add edx, 4 ;Point to dest member
mov eax, [edx] ;Load into eax
shl eax, 2 ;Multiple by 4
lea eax, [distance+eax] ;Access member of distance array
push dword [eax] ;Push eax
push eax ;Push eax pointer
sub edx, 4 ;Point edx to source member
mov eax, [edx] ;Store value at edx in eax
shl eax, 2 ;Multiply by 4
lea eax, [distance+eax] ;Access member of distance array
push dword [eax] ;Store on stack
push eax ;Push eax onto stack
add edx, 8 ;Point to weight member
push dword [edx] ;Push onto stack
push edx ;Push edx onto stack
mov eax, [esp+4] ;Take value off top of stack and store in eax
add eax, [esp+12] ;Add top two dwords on stack
cmp eax, [esp+20] ;Compare with first
jz after ;Jump to label after if eax = [esp+20]
jns label1 ;Looks complicated
jmp label2 ;but is basically
label1: ;the same as
jo after ;the C/C++ equivalent of
jmp start2 ;if(eax < [esp+20])
label2: ;{
jno after ; //Bla bla bla
start2: ;}
mov edx, [esp+16] ;Edx = [esp+16]
mov dword [edx], eax ;Set [edx] = eax
after: ;Label after if clause
add esp, 24 ;Push EVERYTHING off the stack
inc ebx ;Increment loop counter
jmp innerloop1 ;Jump to start of inner loop
end2: ;End of loop label
cmp ecx, 0 ;Check if 0
jz outside ;Break loop
dec ecx ;Decrement ecx
jmp loopend2 ;Jump to start of outer loop
outside:
mov eax, 0 ;Reset the registers
mov ebx, 0 ;Reset the registers
mov ecx, 0 ;Reset the registers
mov edx, 0 ;Reset the registers
mov ecx, [ebp+12] ;Load nodecount parameter
dec ecx ;Decrement ecx
loopstart2: ;Start of loop
mov edx, [ebp+8] ;Load into edx
add edx, ecx ;Add edx and ecx
push edx ;Temporarily store edx on stack
push 12 ;Store multiplier on stack
mov eax, edx ;Store edx in eax
mul dword [esp] ;Multiply eax (ie. edx) by 12
add esp, 4 ;Pop off 12
pop edx ;Pop edx back off
mov edx, eax ;Move the result in eax into edx
add edx, 4 ;Add 4 to access dest member
mov eax, [edx] ;Move value of dest member into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Make it point to index in distance array
push dword [eax] ;Store on stack
sub edx, 4 ;Access source member
mov eax, [edx] ;Move value of source member into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Make it point to index in distance array
push dword [eax] ;Store value on stack
add edx, 8 ;Point to weight member
push dword [edx] ;Push onto stack
mov eax, [esp] ;Store in eax
add eax, [esp+4] ;Add to previous stack value
cmp eax, [esp+8] ;Compare two values
jz cafter ;Jump to label after if eax = [esp+20]
jns clabel1 ;Looks complicated
jmp clabel2 ;but is basically
clabel1: ;the same as
jo cafter ;the C/C++ equivalent of
jmp cstart2 ;if(eax < [esp+8])
clabel2: ;{
jno cafter ; //Bla bla bla
cstart2: ;}
add esp, 8 ;Pop those values off
push format_string1 ;Push format string onto the stack
call _printf ;Call printf()
add esp, 4 ;Pop format string off
push 1 ;Push one onto stack
call _exit ;Quit program
cafter: ;cafter label
cmp ecx, 0 ;Check if ecx is 0
jz exitloop ;If it is, break the loop
dec ecx ;Decrement ecx
jmp loopstart2 ;Jump to the front
exitloop:
mov eax, 0 ;Reset the registers
mov ebx, 0 ;Reset the registers
mov ecx, 0 ;Reset the registers
mov edx, 0 ;Reset the registers
loopstart3: ;Loop label
mov ecx, eax ;Move ecx into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Add distance to eax
push dword [eax] ;Push onto stack
push ecx ;Push onto stack
push dword [ebp+20] ;Push source onto stack
push format_string2 ;Push format string onto stack
call _printf ;Call printf
add esp, 12 ;Pop parameters off the stack
inc ecx ;Increment ecx
cmp ecx, [ebp+16] ;Compare with nodecount
jz outside3 ;Quit if equal
jnz loopstart3 ;Loop to front
outside3:
xor eax,eax ;Normal, no error, return value
ret ;Return
== Applications in routing ==
| |||