Hi all.
I have been having some difficulty trying to compute the mode (the value that appear most often) of an array of bytes, given its length.
I have tried more than one approach, but, besides the fact that it doesnt work 100%, I believe there's a simpler way to go about it.
So, consider, for example, the array
.data
buff BYTE 1, 2, 3, 1, 2, 2, 1, 2, 3, 4, 1, 2, 3
tam DWORD $-buff
CALC_MODE proto arr: byte ptr, len: DWORD
In this case, CALC_MODE should return 2.
Any suggestion is appreciated.
Thanks.
create a second array filled with 0's - let's call it result
it's length has to be the highest value in the first array +1 (length = 5 for the example shown)
then, scan the first array
each time a 1 occurs in the first array, increment result[1]
each time a 2 occurs in the first array, increment result[2]
and so on
mov si,arr
mov cx,len
mov bh,0
loop00: mov bl,[si]
inc si
inc byte ptr result[bx]
loop loop00
when you are done, you have to find the largest value in the result array and convert that to the index value
Another possibility is sort the array and then scan it keeping track of the base address of each change and the number of occurences
eg: 1,1,1,1,2,2,2,2,2,3,3,3,4 lets say buff is @ 403000 and you have a local arry on the stack
whenever the value changes you push the address of ESI on the stack
12FFCC = 403000
12FFC8 = 403004
12FFC4 = 403009
12FFC0 = 40300C
As you go along use EAX as an index pointer of which has the most elements which can be calculated in the loop.
This way your array is never any bigger than the individual values in the array. If this is as clear as mud I'll be happy to provide an example
Quote from: dedndave on January 25, 2010, 09:12:48 PM
create a second array filled with 0's - let's call it result
it's length has to be the highest value in the first array +1 (length = 5 for the example shown)
then, scan the first array
each time a 1 occurs in the first array, increment result[1]
each time a 2 occurs in the first array, increment result[2]
and so on
mov si,arr
mov cx,len
mov bh,0
loop00: mov bl,[si]
inc si
inc byte ptr result[bx]
loop loop00
when you are done, you have to find the largest value in the result array and convert that to the index value
The algorithm you mentioned is exactly what I have thought before.
My problem is, since I am not that experienced in assembly, I can't (yet) think very well in terms of "assembly programming" so I get stuck very often.
As I mentioned I tried to imlpement that algo, but got lost in the middle. Would you be kind enough to post the code? It would be greatly appreciated.
Thanks.
I'm not sure whom you want to replay as it seems you want me to respond but your quoting Dave. Anyway I'll post mine. My code has one problem in that if the value with the greatest number has a duplicate then the first one encountered will be in EDX
You can do your own modification for either word or dword values, but we start with a byte array that's already sorted and upon completion
DH = the value that has the highest number of occurences and DL = How many
.686P
.model flat, stdcall
option casemap :none
.data
Buff db 3,3,3,3,3,3,3,3,10,10,10,10,10,10,10,10,45,45,45,45,45,45,45,45,45,45,45,60,60,60,60,60,60,60
db 71,71,71,71,71,71,71,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,208,208
db 208,208,208,208,208,208,208,208,208,208,208,208,221,221,221,221,221,230,230,230,230,230,0
.code
start:
push esi
mov esi, offset Buff
xor eax, eax
mov ecx, eax
mov edx, ecx
@@: lodsb
.if al != 0
.if ah != al
.if cl > dl
mov dl, cl
mov dh,ah
.endif
mov cl,0
mov ah, al
.endif
inc ecx
jmp @B
.endif
pop esi
ret
end start
My version.
include \masm32\include\masm32rt.inc
.data
Source db 3,3,3,3,3,3,3,3,10,10,10,10,10,10,10,10,45,45,45,45,45,45,45,45,45,45,45
db 60,60,60,60,60,60,60,71,71,71,71,71,71,71
db 101,101,101,100,100,100,100,100,100,100,100,100,100,100,100,100,100
db 208,208,208,208,208,208,208,208,208,208,208,208,208,208
db 221,221,221,221,221,230,230,230,230,230
SourceEnd db 0
.data? ; non-initialised variables
CtBuffer dd 256 dup(?)
.code
start:
mov esi, offset Source
mov edi, offset CtBuffer
mov ecx, SourceEnd-Source ; 82 values in this example
.Repeat
movzx eax, byte ptr [esi+ecx]
inc dword ptr [edi+4*eax]
dec ecx
.Until Zero?
xor edx, edx ; max value count
xor esi, esi ; max value position
mov ecx, 256 ; the whole byte range
.Repeat
mov eax, [edi+4*ecx] ; get the count
.if eax>=edx ; we check downwards
mov esi, ecx ; use "eax>edx" for assigning the mod to
xchg eax, edx ; the higher position in case of equal counts
.endif
dec ecx
.Until Zero?
inkey str$(esi), " is the most frequent value"
invoke ExitProcess, 0
end start
hiyas Jochen, my friend
what - no times ?? :(