system-programming-ngram-algorithm/ngram.asm at main · geceavsar/system-programming-ngram-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

    segment .bss ;declares variables
temp1 resd 1
temp2 resd 1

segment .data ;declare initialized data or constants,
hit dd 0 ;how many matching ngram
counter dd 0 ;to check if n letters are matched
index2 dd 0 ; holds str2 index
index1 dd 0 ;holds str1 index
ngram1 dd 0 ;#of ngram in str1
ngram2 dd 0 ;#of ngram in str2

;;str1 ebp+8
;;size1 ebp+12
;;str2 ebp+16
;;size2 ebp+20
;;n ebp+24

segment .text
global ngram

ngram:
	push ebp
    mov  ebp,esp

	;init counters
	mov dword [hit],0
	mov dword [index1],0

	mov edx, [ebp+16]
	mov ecx, [ebp+8]

	mov esi,0 ; esi = 0
	mov edi,0 ; edi = 0
	mov ebx, [ebp+24] ;ebx = n

	;;calculate #of ngrams for str1
	mov eax, [ebp+12]
	sub eax, ebx
	add eax, 1
	mov dword [ngram1], eax

	;;calculate #of ngrams for str2
	xor eax, eax
	mov eax, [ebp+20]
	sub eax, ebx
	add eax, 1
	mov dword [ngram2], eax

l1:
	mov dword [counter], 0
	push esi
	mov dword [index2],0

l4:
	push eax
	push ebx
	mov byte al, [edx+edi]
	mov byte bl, [ecx+esi]
	cmp al,bl
	pop ebx
	pop eax
	je match

l3:
	inc edi ;increment offset instead of register
	add dword [index2],1 ;increment index 2

	mov eax, [ngram2]
	cmp [index2],eax
	;;check for if str2 reached end
	je l2
	jmp l4

l2:
	pop esi ;pop esi back
	inc esi
	add dword [index1],1 ;increment index 1

	mov eax, [ngram1]
	cmp [index1],eax
	;;check for if str1 reached end
	je fin
	mov edi, 0
	jmp l1

match:
	add dword [counter],1 ;increment counter
	cmp [counter], ebx
	je addHit

	inc esi
	inc edi

	push eax
	push ebx
	mov byte al, [edx+edi]
	mov byte bl, [ecx+esi]
	cmp al,bl
	pop ebx
	pop eax
	je match

	jmp l2

addHit:
	add dword [hit],1 ;increment hit count
	jmp l2

fin:
	mov edi, [ngram1]
	mov esi, [ngram2]
	add edi, esi
	mov esi, 100
	mov eax,[hit] ;;eax is intersection
	xor edx, edx ;;clear edx
    sub edi, eax ;;edi is union
    cmp edi, 0
    je noCalc

	mul esi
	div edi
noCalc:
    pop ebp
    ret